Arboles de Decisión para Regresión y Clasificación¶

Indice¶

  • Trees

  • Regression Trees

    • Algoritmo de particion binaria
    • Ejemplo de juguete
    • Penalized Regression Trees
  • Regression Trees in Python
    • Algoritmo de creacion propia
      • Testeo del algoritmo
      • Validacion Simple con funcion propia
    • Regression Trees in Sklearn
  • Classsification Trees
    • Algoritmo de particion binaria
  • Classsification Trees in Python
    • Algoritmo de creacion propia con TEC
      • Testeo del algoritmo
    • Algoritmo de creacion propia con Gini
      • Testeo del algoritmo
    • Classification Trees in Sklearn

Trees ¶

Vamos a considerar el siguiente tipo de arboles (matematicos):

In [ ]:
import warnings
warnings.filterwarnings("ignore")
In [ ]:
from IPython.display import Image
Image(filename='arbol.jpg', width = 1000, height = 400) 
Out[ ]:

Es importante tener en cuenta los elementos que estan reflejados, pues los usaremos posteriormente.

Los arboles estan compuestos de iteraciones, que a su vez cada una de ellas se dividen en dos tallos. La union de tallos de distintas iteraciones da lugar a las ramas del arbol.


Regression Trees ¶

La idea de los algoritmos de arboles de regresion es segmentar las observaciones de los predictores $X_1,...,X_p$ para predecir el valor de la respuesta $Y$ en base a esa informacion segmentada. Es algo asi como predecir $Y$ por grupos/segmentos.

Definicion formal de un arbol de regresion:¶

Elementos Básicos¶

  • Tenemos unos predictores $\hspace{0.1cm} X_1,...,X_p \hspace{0.1cm}$ y una variable respuesta cuantitativa $\hspace{0.1cm}Y$
  • Tenemos un arbol $\hspace{0.1cm} T \hspace{0.1cm}$ de la forma del expuesto en la imagen con $\hspace{0.1cm} m-1 \hspace{0.1cm}$ iteraciones y $\hspace{0.1cm} m \hspace{0.1cm}$ ramas.
  • $r_{ht}\hspace{0.1cm}$ es la rama $h$ del arbol con $t$ iteraciones.
  • Cada iteracion del arbol tiene asociado uno de los predictores $\hspace{0.07cm} X_1,...,X_n$
  • Cada iteracion del arbol tiene dos tallos (tallo 1 (izquierdo) y tallo 2 (derecho)).
  • En cada tallo de una iteracion se define un intervalo.

  • $\hspace{0.1cm} I_{lt} \hspace{0.1cm}$ es el intervalo asociado al tallo $l$ de la iteracion $\hspace{0.1cm} t$ , con $\hspace{0.1cm}l = 0,1$

  • Para simplificar el problema consideraremos $\hspace{0.1cm} I_{1t} = (-\infty \hspace{0.03cm},\hspace{0.03cm} s_t)\hspace{0.1cm}$ y $\hspace{0.1cm} I_{2t} = [s_t \hspace{0.03cm},\hspace{0.03cm} \infty]\hspace{0.1cm}$ donde $\hspace{0.1cm} s_t \hspace{0.1cm}$ es llamado punto de corte de la iteracion $\hspace{0.1cm} t \hspace{0.1cm}$ del arbol
  • $R_{ht} \hspace{0.1cm}$ es la region (rectangulo $p$-dimensional) definida por la rama $\hspace{0.1cm} h \hspace{0.1cm}$ de un arbol con $t$ iteraciones

Por ejemplo, considerando el arbol de arriba:

$R_{17} = \lbrace (v_1,...,v_p) \hspace{0.15cm}/\hspace{0.15cm} v_2 \in I_{11} \hspace{0.15cm} \text{y} \hspace{0.15cm} v_2 \in I_{12} \hspace{0.15cm} \text{y} \hspace{0.15cm} v_1 \in I_{14} \hspace{0.15cm} \rbrace \hspace{0.1cm}$

$R_{57} = \lbrace (v_1,...,v_p) \hspace{0.15cm}/\hspace{0.15cm} v_2 \in I_{21} \hspace{0.15cm} \text{y} \hspace{0.15cm} v_3 \in I_{13} \hspace{0.15cm} \text{y} \hspace{0.15cm} v_4 \in I_{16} \hspace{0.15cm} \rbrace \hspace{0.1cm}$


Criterio de prediccion de la variable respuesta¶

Dada una nueva observacion $\hspace{0.1cm} x_{new}= (x_{new,1},x_{new,2},...,x_{new,p} ) \hspace{0.1cm}$ la idea es predecir $\hspace{0.1cm} y_{new} \hspace{0.1cm}$ como sigue:

$$Si \hspace{0.3cm} x_{new} \in R_{ht} \hspace{0.22cm} \Rightarrow \hspace{0.22cm} \widehat{y}_{new} = \widehat{y}_{R_{ht}} = \dfrac{1}{\# \lbrace i / x_i \in R_{ht} \rbrace} \cdot \sum_{i / x_i \in R_{ht}} y_i $$

Es decir, para una observacion que cae en la rama $R_{ht}$ el modelo predice su valor de la respuesta como la media de los valores de la respuesta de las observaciones de train que pertenecen a esa misma rama.

$\widehat{y}_{R_{ht}}$ es la prediccion de la variable respuesta que un arbol de regresion con $t$ iteraciones hace para las observaciones que caen en la rama $h$ de dicho arbol.


Objetivo¶

Definimos el error de entrenamiento de la rama $h$ de un arbol de regresion con $t$ iteraciones como el error cometido por ese arbol de regresion al predecir la respuesta para las observaciones de entrenamiento que caen en la rama $h$ , y esto se mide como la suma de los cuadrados de los errores de prediccion de la respuesta para las observaciones que caen en la rama $h$ :

$$SSR(R_{ht}) = \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{ht} } (y_i - \widehat{y}_{R_{ht}})^2$$

Observación:

El error de prediccion de la respuesta para un individuo $i$ de la muestra tal que $\hspace{0.1cm} x_i \in R_{ht} \hspace{0.1cm}$ es $\hspace{0.1cm} y_i - \widehat{y}_{R_{ht}} \hspace{0.1cm}$ , ya que $\hspace{0.1cm} \widehat{y}_{R_{ht}} \hspace{0.1cm}$ es la prediccion de la respuesta que este modelo hace para los individuos que caen en $R_{ht}$ $\hspace{0.1cm}($ cuyas observaciones de los predictores, $\hspace{0.1cm}x_i\hspace{0.1cm}$, caen en $\hspace{0.1cm}R_{ht})$

Definimos el error global de entrenamiento de un arbol de regresion con $t$ iteraciones como la suma de los errores de entrenamiento de las ramas de ese arbol de regresion:

$$\sum_{h=1}^{m} \hspace{0.1cm} SSR(R_{ht}) $$

El objetivo es construir un arbol de regresion con con $t$ iteraciones y $m$ ramas tal que minimice el error global de entrenamiento.

Es decir, formalmente el objetivo es:

$$ \underset{R_{1t},..,R_{mt}}{Min} \hspace{0.12cm} \sum_{h=1}^{m} \hspace{0.1cm} SSR(R_{ht}) $$

Pero para escoger las regiones $\hspace{0.1cm} R_{1t},...,R_{mt} \hspace{0.1cm}$ que definen las ramas del arbol hay que determinar dos elementos que definen a su vez a las regiones:

$1.\hspace{0.1cm}$ Qué predictores estan asociados a cada iteracion del arbol $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ Para cada iteracion $i$ escoger $X_j \hspace{0.01cm}$ $(\hspace{0.01cm} $ es decir, escoger $j \hspace{0.01cm})$

$2.\hspace{0.1cm}$ Qué intervalos estan asociados a cada uno de los dos tallos de cada interaccion $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ Para cada iteracion $t$ escoger $I_{1t}$ y $I_{2t}\hspace{0.1cm}$ $(\hspace{0.01cm}$ es decir, escoger el punto de corte $\hspace{0.07cm}s_t \hspace{0.04cm} )$

Por tanto el porblema a resolver se puede reformular como:

Para cada iteracion $\hspace{0.1cm} t \hspace{0.1cm}$ escoger $\hspace{0.1cm} X_j\hspace{0.01cm}$ $(\hspace{0.05cm}$ es decir $\hspace{0.01cm}j \hspace{0.05cm})\hspace{0.05cm}$ y el par de intervalos $\hspace{0.05cm}( I_{1t}\hspace{0.1cm},\hspace{0.1cm}I_{2t} )\hspace{0.1cm}$ $\hspace{0.1cm}($ es decir $\hspace{0.1cm} s_t)\hspace{0.1cm}$ tal que se acaben formando un arbol cuyas $m$ ramas definan unas regiones $\hspace{0.1cm}R_{1t},...,R_{mt}\hspace{0.1cm}$ que minimicen $\hspace{0.1cm}\sum_{h=1}^{m} SSR(R_{ht})$


Algoritmo para la resolucion del problema $\hspace{0.1cm}\Rightarrow\hspace{0.1cm}$ Algoritmo de particion binaria ¶

El siguiente algoritmo es una forma de resolver el problema planteado anteriormente. Consiste en ir generando el arbol de manera secuencial, iteracion a iteracion, minimizando en cada paso el error de prediccion de la respuesta para las observaciones de train que caen en las ramas asociadas a la iteracion en cuestion que esta siendo optimizada. La idea es generar cada iteracion del arbol minimizando los errores de prediccion de la respuesta para len cada rama, hasta que se cumple un criterio de parada en el que no se generan mas iteraciones y el arbol queda finalizado.

El algoritmo se basa en la resolucion secuencial de problemas de minimizacion, uno por cada iteracion tenga el arbol que se acabará generando.


Problema de la Iteracion 1¶

Arbol con 1 iteracion:

In [ ]:
from IPython.display import Image
Image(filename='arbol 1iter.jpg', width = 600, height = 300) 
Out[ ]:

La idea es, determinar las regiones $R_{11}$ y $R_{21}\hspace{0.1cm}$ $($ es decir, $j$ y $s_1 \hspace{0.05cm}) \hspace{0.1cm}$ del arbol con 1 iteracion tal que minimizan el error de entrenamiento global de dicho arbol con 1 iteracion.


Mas formalmente el problema planteado es:

$$ \underset{R_{11} , R_{21}} {Min} \hspace{0.15cm} \left(\hspace{0.1cm} SSR_1 = SSR(R_{11}) + SSR(R_{21}) \hspace{0.1cm}\right) \hspace{0.1cm} = \\[25pt] =\hspace{0.2cm} \underset{R_{11} , R_{21}} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{11} } (y_i - \widehat{y}_{R_{11}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{21} } (y_i - \widehat{y}_{R_{21}})^2 \hspace{0.2cm} \right) \\[25pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_1} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_1 } (y_i - \widehat{y}_{R_{11}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_1 } (y_i - \widehat{y}_{R_{21}})^2 \hspace{0.2cm} \right) $$

Notar que:

$R_{11} = \lbrace (v_1 ,..., v_p) / v_j < s_1 \rbrace \hspace{0.3cm}\Rightarrow\hspace{0.3cm} [\hspace{0.1cm} x_i=(x_{i1},...,x_{ip}) \in R_{11} \hspace{0.1cm} \Leftrightarrow \hspace{0.1cm} x_{ij} < s_1 \hspace{0.1cm}] \hspace{0.3cm}\Rightarrow\hspace{0.3cm} \lbrace i/x_i \in R_{11} \rbrace = \lbrace i / x_{ij} < s_1 \rbrace$

$ R_{12} = \lbrace (v_1 ,..., v_p) / v_j \geqslant s_1 \rbrace \hspace{0.3cm}\Rightarrow\hspace{0.3cm} [\hspace{0.1cm} x_i=(x_{i1},...,x_{ip}) \in R_{21} \hspace{0.1cm} \Leftrightarrow \hspace{0.1cm} x_{ij} \geqslant s_1 \hspace{0.1cm}] \hspace{0.3cm}\Rightarrow\hspace{0.3cm} \lbrace i/x_i \in R_{21} \rbrace = \lbrace i / x_{ij} \geqslant s_1 \rbrace$

Notese que determinar $R_{11}$ y $R_{21}$ es equivalente a determinar el predictor $X_j$ $($ es decir $j)$ y el punto de corte $s_1$ asociados a la Iteracion 1, ya que $R_{11}$ y $R_{21}$ quedan determinadas al fijar $X_j$ y $s_1$

Donde :

  • $\hspace{0.2cm} j \in \lbrace 1,2,...,p \rbrace $
  • Si $X_j$ es cuantitativa:

$\hspace{0.7cm}$ Ordenamos las observaciones de $X_j$ y quitamos repeticiones, obtenemos $X_j^{order}$, entonces:

$$ s_1 \in \Biggl\{ \dfrac{ x_{(1)j} + x_{(2)j} }{2} \hspace{0.1cm}, \hspace{0.1cm} \dfrac{x_{(2)j} + x_{(3)j} }{2} \hspace{0.1cm} ,...,\hspace{0.1cm} \dfrac{x_{(n-1)j} + x_{(n)j} }{2} \Biggl\}$$

$\hspace{0.7cm}$ Donde $\hspace{0.1cm} x_{(i)j} \hspace{0.1cm} $ es la observacion que ocupa la posicion $i$-esima en $\hspace{0.1cm} X_j^{order}$

  • Si $X_j$ es categorica con $c$ categorias:
$$ s_1 \in Rango(X_j) = \lbrace 0,1,..., c-1 \rbrace $$

Notese que la eleccion de $X_j$ determina el campo de variacion de $s_1$

  • $SSR(R_{11})$ es el error de entrenamiento de la rama $1$ de un arbol de regresion con 1 iteracion

  • $SSR(R_{21})$ es el error de entrenamiento de la rama $2$ de un arbol de regresion con 1 iteracion

Por otro lado:

$$\widehat{y}_{R_{11}} \hspace{0.1cm} = \hspace{0.1cm} \dfrac{1}{\# \lbrace i / x_i \in R_{11} \rbrace} \cdot \sum_{i / x_i \in R_{11}} y_i \hspace{0.1cm} = \hspace{0.1cm} \dfrac{1}{\# \lbrace i / x_{ij} < s_1 \rbrace} \cdot \sum_{i / x_i < s_1} y_i $$
$$\widehat{y}_{R_{21}} \hspace{0.1cm} = \hspace{0.1cm} \dfrac{1}{\# \lbrace i / x_i \in R_{21} \rbrace} \cdot \sum_{i / x_i \in R_{21}} y_i \hspace{0.1cm} = \hspace{0.1cm} \dfrac{1}{\# \lbrace i / x_i \geqslant s_1 \rbrace} \cdot \sum_{i / x_i \geqslant s_1} y_i $$

$\widehat{y}_{R_{11}}$ es la prediccion de la respuesta dada por un arbol de regresion con 1 Iteracion para las observaciones que caen en la rama 1 de dicho arbol.

$\widehat{y}_{R_{21}}$ es la prediccion de la respuesta dada por un arbol de regresion con 1 Iteracion para las observaciones que caen en la rama 2 de dicho arbol.

Estos elementos no volveran a ser definidos en los sucesivos problemas de iteracion para no pecar de ser repetitivo, puesto que pueden ser facilmente extrapolados a cualquier problema de iteracion. Ademas las definiciones generales de estos elementos han sido expuestas ya anteriormente.

  • Denotaremos por $\hspace{0.1cm} \left(\hspace{0.1cm} j^{*(i)} \hspace{0.05cm},\hspace{0.05cm} s^{*(i)} \hspace{0.1cm}\right) \hspace{0.1cm}$ a una solucion del problema de la Iteracion $i$ , para $i=1,...,m-1$

Arbol obtenido tras resolver el problema de la Iteracion 1:

In [ ]:
from IPython.display import Image
Image(filename='iter1.jpg', width = 600, height = 300) 
Out[ ]:
  • Si alguna de las ramas del arbol resultante de resolver el problema la iteracion 1 tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2

Notese que $k$ será un hiperparametro del algoritmo.


Problema de la Iteracion 2¶

Arbol con 2 iteraciones tras resolver el problema anterior:

In [ ]:
from IPython.display import Image
Image(filename='arbol 2iter.jpg', width = 600, height = 300) 
Out[ ]:

Si estamos en este problema es porque ninguna rama del arbol resultante del problema de la Iteracion 1 tiene menos de $k$ observaciones

La idea es, determinar las regiones $R_{12}$ , $R_{22}$ y $R_{32}$ del arbol con 2 iteraciones (es decir, $j$ y $s_2$), considerando la solucion del problema de la iteracion 1 (arbol de arriba) , que minimizan el error de entrenamiento global de dicho arbol.

Notese que $R_{32}$ ya esta determinada tras la resolucion del problema anterior, por ello realmente solo hay que determinar las regiones $R_{12}$ y $R_{22}$ óptimas (a saber, $j$ y $s_2$ óptimos)


Mas formalmente el problema planteado es:

$$ \underset{R_{12} , R_{22}, R_{32}} {Min} \hspace{0.15cm} \left(\hspace{0.1cm} SSR_2 = SSR(R_{12}) + SSR(R_{22}) + SSR(R_{32}) \hspace{0.1cm}\right) \hspace{0.1cm} = \\[35pt] =\hspace{0.2cm} \underset{R_{12} , R_{22}, R_{32}} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{12} } (y_i - \widehat{y}_{R_{12}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{22} } (y_i - \widehat{y}_{R_{22}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{32} } (y_i - \widehat{y}_{R_{32}})^2 \hspace{0.2cm} \right) \\[35pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_2} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ \substack{ i \hspace{0.05cm} / \hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij } \hspace{0.05cm} < \hspace{0.05cm} s_2} } (y_i - \widehat{y}_{R_{12}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 } } (y_i - \widehat{y}_{R_{22}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} } } (y_i - \widehat{y}_{R_{32}})^2 \hspace{0.2cm} \right) \\[45pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_2} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ \substack{ i \hspace{0.05cm} / \hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij } \hspace{0.05cm} < \hspace{0.05cm} s_2} } (y_i - \widehat{y}_{R_{12}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 } } (y_i - \widehat{y}_{R_{22}})^2 \hspace{0.2cm} \right) $$

Notese que el sumando:

$$ \sum_{i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} } (y_i - \widehat{y}_{R_{32}})^2 $$

NO depende de $(j, s_2)$ , por lo que puede sacarse de la funcion objetivo del problema de minimizacion sin que esto altere la solucion del problema.


Arbol tras resolver el problema de la Iteracion 2:

In [ ]:
from IPython.display import Image
Image(filename='iter2.jpg', width = 940, height = 320)
Out[ ]:
  • Si alguna de las ramas tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2


Problema de la Iteracion 3¶

Arbol con 3 iteraciones tras resolver el problema anterior:

In [ ]:
from IPython.display import Image
Image(filename='arbol 3iter.jpg', width = 940, height = 320)
Out[ ]:

Si estamos en este problema es porque ninguna rama del arbol resultante del problema de la Iteracion 2 tiene menos de $k$ observaciones

La idea es, determinar las regiones $R_{13}$ , $R_{23}$, $R_{33}$ y $R_{43}$ del arbol con 3 iteraciones $($ es decir, $j$ y $s_3 \hspace{0.05cm})$, considerando la solucion del problema de la iteracion 2 (arbol de arriba), que minimizan el error de entrenamiento global de dicho arbol.

Notese que $R_{13}$ y $R_{23}$ ya están determinadas tras la resolucion del problema anterior, por ello realmente solo hay que determinar las regiones $R_{33}$ y $R_{43}$ óptimas (a saber, $j$ y $s_3$ óptimos)


Mas formalmente el problema se plantea como sigue:

$$ \underset{R_{13} , R_{23}, R_{33}, R_{43}} {Min} \hspace{0.15cm} \left(\hspace{0.1cm} SSR_3 = SSR(R_{13}) + SSR(R_{23}) + SSR(R_{33}) + SSR(R_{43}) \hspace{0.1cm}\right) \hspace{0.1cm} = \\[35pt] =\hspace{0.2cm} \underset{R_{13} , R_{23}, R_{33}, R_{43}} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{13} } (y_i - \widehat{y}_{R_{13}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{23} } (y_i - \widehat{y}_{R_{23}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{33} } (y_i - \widehat{y}_{R_{33}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{43} } (y_i - \widehat{y}_{R_{43}})^2 \hspace{0.2cm} \right) \\[35pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_3} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)} } \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} } } (y_i - \widehat{y}_{R_{13}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(2)} } } (y_i - \widehat{y}_{R_{23}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 } } (y_i - \widehat{y}_{R_{33}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 } } (y_i - \widehat{y}_{R_{43}})^2 \hspace{0.2cm} \right) \\[45pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_3} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 } } (y_i - \widehat{y}_{R_{33}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 } } (y_i - \widehat{y}_{R_{43}})^2 \hspace{0.2cm} \right) $$

Notese que los sumandos :

$$ \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ x_{ij^{*(2)} } \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} }} (y_i - \widehat{y}_{R_{13}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ x_{ij^{*(2)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(2)} } } (y_i - \widehat{y}_{R_{23}})^2 $$

NO dependen de $(j, s_3)$ , por lo que puede sacarse de la funcion objetivo del problema de minimizacion sin que esto altere la solucion del problema.


Arbol tras resolver el problema de la Iteracion 3

In [ ]:
from IPython.display import Image
Image(filename='iter3.jpg', width = 900, height = 300)
Out[ ]:
  • Si alguna de las ramas tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2


*Problema de la Iteracion 4:*

Arbol con 4 iteraciones tras resolver el problema anterior:

In [ ]:
from IPython.display import Image
Image(filename='arbol 4iter.jpg', width = 900, height = 400)
Out[ ]:

Si estamos en este problema es porque ninguna rama del arbol resultante del problema de la Iteracion 3 tiene menos de $k$ observaciones

La idea es, determinar las regiones $R_{14}$ , $R_{24}$, $R_{34}$ , $R_{44}$, $R_{54}$ del arbol con 4 iteraciones $($ es decir, $j$ y $s_4 \hspace{0.1cm} )$, considerando la solucion del problema de la iteracion 3(arbol de arriba), que minimizan el error de entrenamiento global de dicho arbol.

Notese que $R_{34}$ , $R_{44}$ y $R_{54}$ ya están determinadas tras la resolucion de los problemas anteriores, por ello realmente solo hay que determinar las regiones $R_{14}$ y $R_{24}$ óptimas (a saber, $j$ y $s_4$ óptimos)


Mas formalmente el problema se plantea como sigue:

$$ \underset{R_{14} , R_{24}, R_{34}, R_{44}, R_{54} } {Min} \hspace{0.15cm} \hspace{0.1cm} SSR_4 = SSR(R_{14}) + SSR(R_{24}) + SSR(R_{34}) + SSR(R_{44}) + SSR(R_{54}) \hspace{0.1cm} \hspace{0.1cm} = \\[35pt] =\hspace{0.2cm} \underset{R_{14} , R_{24}, R_{34}, R_{44}, R_{54} } {Min} \hspace{0.2cm} \left( \hspace{0.2cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{14} } } (y_i - \widehat{y}_{R_{14}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{24} } (y_i - \widehat{y}_{R_{24}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{34} } (y_i - \widehat{y}_{R_{34}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{44} } (y_i - \widehat{y}_{R_{44}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ i \hspace{0.05cm}/\hspace{0.05cm} x_i \in R_{54} } (y_i - \widehat{y}_{R_{54}})^2 \hspace{0.2cm} \right) \\[35pt] = \hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_4} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{\substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} \\ \\ x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_4 } } (y_i - \widehat{y}_{R_{14}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} \\ \\ x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_4 } } (y_i - \widehat{y}_{R_{24}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(2)} } } (y_i - \widehat{y}_{R_{34}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(3)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(3)} } } (y_i - \widehat{y}_{R_{44}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(3)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(3)} } } (y_i - \widehat{y}_{R_{54}})^2 \hspace{0.2cm} \right) \\[45pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_4} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} \\ \\ x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_4 } } (y_i - \widehat{y}_{R_{14}} )^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} \\ \\ x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_4 } } (y_i - \widehat{y}_{R_{24}})^2 \hspace{0.2cm} \right) $$

Notese que los sumandos:

$$ \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(2)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(2)} } } (y_i - \widehat{y}_{R_{34}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(3)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(3)} } } (y_i - \widehat{y}_{R_{44}})^2 \hspace{0.3cm} + \hspace{0.1cm} \sum_{ \substack{ i \hspace{0.05cm}/\hspace{0.05cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \\ \\ x_{ij^{*(3)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(3)} } } (y_i - \widehat{y}_{R_{54}})^2$$

NO dependen de $(j, s_4)$ , por lo que puede sacarse de la funcion objetivo del problema de minimizacion sin que esto altere la solucion del problema.


Arbol tras resolver el problema de la Iteracion 4

In [ ]:
from IPython.display import Image
Image(filename='iter4.jpg', width = 980, height = 350)
Out[ ]:
  • Si alguna de las ramas tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2

Siempre que no se cumpla la condición de parada se seguiria haciendo crecer el arbol generando nuevas iteraciones.

No seguiremos exponiendo mas iteraciones del algoritmo, puesto que es facilmente extrapolable lo expuesto a cualquier iteracion superior.


Ejemplo de juguete ¶

Ilustraremos con un ejemplo de juguete cómo es el funcionamiento del algoritmo expuesto. Especialmente la resolucion de los problemas de iteracion.


Arboles de Regresion Penalizados ¶


Regression Trees in Python ¶

Algoritmo Regression Tree de creacion propia en Python ¶

In [ ]:
def regression_tree(Data_set, iterations_vector, k):

# POR AHORA SOLO GENERA 4 ITERACIONES EN EL ARBOL --> iterations_vector = range(1,5) como mucho (=[1,2,3,4])

########################################################################
    
# Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p
# Ademas las variables categoricas deben ser type=0bject , mientras que las cuantitativas type=int64 or float64


    def s_values(j, Data_set):

        s_values = []

        if  (Data_set.dtypes[j] != 'float64') & (Data_set.dtypes[j] != 'int64') : # Para las variables categoricas s_value sera simplemente su rango.

            s_values = Data_set.sort_values(by=[Data_set.columns[j]], axis=0, ascending=True, ignore_index=True).iloc[:, j].unique()


        elif (Data_set.dtypes[j] == 'float64') | (Data_set.dtypes[j] == 'int64') :

            Xj_sorted = Data_set.sort_values(by=[Data_set.columns[j]], axis=0, ascending=True, ignore_index=True).iloc[:, j].unique()

        
            for i in range(0, len(Xj_sorted)-1):

                s_values.append( (Xj_sorted[i] + Xj_sorted[i+1] ) / 2  )

    
        return s_values


########################################################################  

   ## ITERACION 1

    if iterations_vector[0] == 1 : # nacimiento del arbol

        def RSS_1(j,s, Data_set):

         # Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p

    ######################################

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_r11 = ( len( Data_set.loc[ Data_set.iloc[:, j] < s  , 'Y' ] ) != 0 )
            cond_r21 = ( len( Data_set.loc[ Data_set.iloc[:, j] >= s , 'Y' ] ) != 0 )


            if (cond_r11 == False) | (cond_r21 == False) :

                RSS_1 = math.inf

            elif  (cond_r11 == True) & (cond_r21 == True) : 

                y_i_r11 = Data_set.loc[ (Data_set.iloc[:, j] < s) , 'Y' ]

                y_r11 = y_i_r11.sum() / len( y_i_r11 )  
   
                
                y_i_r21 = Data_set.loc[ (Data_set.iloc[:, j] >= s) , 'Y' ]  

                y_r21 = y_i_r21.sum() / len( y_i_r21 )
           
                
                RSS_11 = ( (y_i_r11 - y_r11 )**2 ).sum()

                RSS_12 = ( (y_i_r21 - y_r21 )**2 ).sum()

                RSS_1 = RSS_11 + RSS_12

            ############

            return(RSS_1)


      ################################################

        ## Busqueda de j_star y s_star de la iteracion 1

        RSS_vector = []
        j_vector = []
        s_vector = []

        s_star_vector = []
        j_star_vector = []
        RSS_star_vector = []

        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                RSS_vector.append( RSS_1(j, s, Data_set) )

                j_vector.append( j )

                s_vector.append( s )

        RSS_df = pd.DataFrame({'RSS':RSS_vector, 'j':j_vector, 's':s_vector})

        RSS_df_sorted = RSS_df.sort_values(by=['RSS'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( RSS_df_sorted.loc[0, 's'] )
        j_star_vector.append( RSS_df_sorted.loc[0, 'j'] )
        RSS_star_vector.append(RSS_df_sorted.loc[0, 'RSS'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...    
        
      ###################################

        # Condicion de parada:

        obs_r11 = len( Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0] , : ] )
        obs_r21 = len( Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0] , : ] )

        if(obs_r11 < k) | (obs_r21 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 1 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations=1

            obs_ramas = [obs_r11 , obs_r21]


           

            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas ) 

            ###################

        elif (obs_r11 >= k) & (obs_r21 >= k) : # No se cumple el criterio de parada

            pass


   ######################################################################################

    ## ITERACION 2

    if iterations_vector[1] == 2 :  # Desarrollar nodo R1 de la 1ª iteracion

        ################################################################

        def RSS_2(j,s, Data_set):    # Desarrollar nodo R1 de la 1ª iteracion --> considerar j_star_vector[0] y s_star_vector[0] (1ª iteracion) y < (R1)

         # Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p

           ################

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_r12 = ( len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] < s) , 'Y' ] ) != 0 )
            cond2_r22 = ( len( Data_set.loc[ (Data_set.iloc[:, j] >= s) & (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) , 'Y' ] ) != 0 )
              

            if (cond_r12 == False) | (cond2_r22 == False) :

                RSS_2 = math.inf

            elif  (cond_r12 == True) & (cond2_r22 == True) : 

                y_i_r12 = Data_set.loc[  (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] < s) , 'Y' ]

                y_r12 = y_i_r12.sum() / len( y_i_r12 )  
   
                
                y_i_r22 = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] >= s)  , 'Y' ]  

                y_r22 = y_i_r22.sum() / len( y_i_r22 )
           
                
                RSS_21 = ( (y_i_r12 - y_r12 )**2 ).sum()

                RSS_22 = ( (y_i_r22 - y_r22 )**2 ).sum()

                RSS_2 = RSS_21 + RSS_22

            ############

            return(RSS_2)


      ###########################################

      # Busqueda de j_star y s_star de la iteracion 2:

        RSS_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                RSS_vector.append( RSS_2(j, s, Data_set) )

                j_vector.append( j )

                s_vector.append( s )

        RSS_df = pd.DataFrame({'RSS':RSS_vector, 'j':j_vector, 's':s_vector})

        RSS_df_sorted = RSS_df.sort_values(by=['RSS'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( RSS_df_sorted.loc[0, 's'] )
        j_star_vector.append( RSS_df_sorted.loc[0, 'j'] )
        RSS_star_vector.append(RSS_df_sorted.loc[0, 'RSS'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...


      ###################################

        # Condicion de parada:

        obs_r12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] )
        obs_r22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )
        obs_r32 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) , : ] )

        if(obs_r12 < k) | (obs_r22 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 2 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations=2
            
            obs_ramas = [obs_r12 , obs_r22, obs_r32]


           
            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas ) 

            ###################


        elif (obs_r12 >= k) & (obs_r22 >= k) : # No se cumple el criterio de parada

            pass



####################################################################################

## ITERACION 3

    if iterations_vector[2] == 3 :  # Desarrollar nodo R2 de la 1ª iteracion -->  considerar j_star_vector[0] y s_star_vector[0] (1ª iteracion) y >= (R2)

       #########################################

        def RSS_3(j,s, Data_set):    

         # Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p

           ################

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_r33 = ( len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] < s)  , 'Y' ] ) != 0 )
            cond_r43 = ( len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] >= s) , 'Y' ] ) != 0 )
              

            if (cond_r33 == False) | (cond_r43 == False) :

                RSS_3 = math.inf

            elif  (cond_r33 == True) & (cond_r43 == True) : 

                y_i_r33 = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] < s)  , 'Y' ]

                y_r33 = (y_i_r33).sum() / len( y_i_r33 )  
   
                
                y_i_r43 = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] >= s)   , 'Y' ]  

                y_r43 = (y_i_r43).sum() / len( y_i_r43 )
           
                
                RSS_31 = ( (y_i_r33 - y_r33 )**2 ).sum()

                RSS_32 = ( (y_i_r43 - y_r43 )**2 ).sum()

                RSS_3 = RSS_31 + RSS_32
            

            ############

            return(RSS_3)


       ###########################################

      # Busqueda de j_star y s_star de la iteracion 3:

        RSS_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                RSS_vector.append( RSS_3(j, s, Data_set) )

                j_vector.append( j )

                s_vector.append( s )

        RSS_df = pd.DataFrame({'RSS':RSS_vector, 'j':j_vector, 's':s_vector})

        RSS_df_sorted = RSS_df.sort_values(by=['RSS'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( RSS_df_sorted.loc[0, 's'] )
        j_star_vector.append( RSS_df_sorted.loc[0, 'j'] )
        RSS_star_vector.append(RSS_df_sorted.loc[0, 'RSS'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...


      ###################################

        # Condicion de parada:

        obs_r13 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] )
        obs_r23 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )

        obs_r33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] )
        obs_r43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] )


        if(obs_r33 < k) | (obs_r43 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations = 3
            
            obs_ramas = [obs_r13, obs_r23, obs_r33 , obs_r43]


           

            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas ) 

            ###################


        elif (obs_r33 >= k) & (obs_r43 >= k) : # No se cumple el criterio de parada

            pass

    #######################


    ## ITERACION 4

    if iterations_vector[3] == 4 :  

       #########################################

        def RSS_4(j,s, Data_set):    

         # Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p

           ################

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_r14 = ( len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) &  (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) &  (Data_set.iloc[:, j] < s) , 'Y' ] ) != 0 )
            cond_r24 = ( len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) &  (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) &  (Data_set.iloc[:, j] >= s) , 'Y' ] ) != 0 )
              

            if (cond_r14 == False) | (cond_r24 == False) :

                RSS_3 = math.inf

            elif  (cond_r14 == True) & (cond_r24 == True) : 

                y_i_r14 = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] < s)  , 'Y' ]

                y_r14 = (y_i_r14).sum() / len( y_i_r14 )  
   
                
                y_i_r24 = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] >= s)   , 'Y' ]  

                y_r24 = (y_i_r24).sum() / len( y_i_r24 )
           
                
                RSS_41 = ( (y_i_r14 - y_r14 )**2 ).sum()

                RSS_42 = ( (y_i_r24 - y_r24 )**2 ).sum()

                RSS_4 = RSS_41 + RSS_42
            

            ############

            return(RSS_4)


       ###########################################

      # Busqueda de j_star y s_star de la iteracion 4:

        RSS_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                RSS_vector.append( RSS_4(j, s, Data_set) )

                j_vector.append( j )

                s_vector.append( s )

        RSS_df = pd.DataFrame({'RSS':RSS_vector, 'j':j_vector, 's':s_vector})

        RSS_df_sorted = RSS_df.sort_values(by=['RSS'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( RSS_df_sorted.loc[0, 's'] )
        j_star_vector.append( RSS_df_sorted.loc[0, 'j'] )
        RSS_star_vector.append(RSS_df_sorted.loc[0, 'RSS'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...


      ###################################

        # Condicion de parada:

        obs_r14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] < s_star_vector[3]) , : ] )
        obs_r24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] >= s_star_vector[3]) , : ] )

        obs_r34 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )
        obs_r44 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] )
        obs_r54 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] )


        if(obs_r14 < k) | (obs_r24 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations = 4
            
            obs_ramas = [obs_r14, obs_r24, obs_r34 , obs_r44, obs_r54]


          

            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas ) 

            ###################


        elif (obs_r14 >= k) & (obs_r24 >= k) : # No se cumple el criterio de parada

            print('Se ha generado el arbol mas grande permitido por el algoritmo (arbol con 4 Iteraciones)')

        # Aunque no se haya cummplido el criterio de parada como esta es la ultima Iteracion contemplada por el algoritmo, 
        # debemos calcular las metricas finales para que sean escupidas por el algoritmo. 
            
            number_iterations=4
            
            obs_ramas = [obs_r14, obs_r24, obs_r34, obs_r44, obs_r54]

            
              
            pass

    #######################
        
   
    return( number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas ) 
In [ ]:
def regression_tree_PREDICTIONS(Data_set, number_iterations, j_star_vector, s_star_vector, obs_ramas, x_new):

    if number_iterations == 1 :

            obs_r11 = obs_ramas[0]
            obs_r21 = obs_ramas[1]


        ### Prediccion:

            # Si x_new cae en r11 

            if x_new[j_star_vector[0] - 1] < s_star_vector[0] :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0] , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r11

            
            # Si x_new cae en r21

            elif x_new[j_star_vector[0] - 1] >= s_star_vector[0] :

                y_new_predict = Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0] , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r21

            

        
    if number_iterations == 2 :

            obs_r12 = obs_ramas[0]
            obs_r22 = obs_ramas[1]
            obs_r32 = obs_ramas[2]


        ### Prediccion:

            # Si x_new cae en r12

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] < s_star_vector[1]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r12

            
            # Si x_new cae en r22

            elif (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] >= s_star_vector[1])  :

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] >= s_star_vector[1]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r22

            # Si x_new cae en r32

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) :

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r32

        
    if number_iterations == 3:

            obs_r13 = obs_ramas[0]
            obs_r23 = obs_ramas[1]
            obs_r33 = obs_ramas[2]
            obs_r43 = obs_ramas[3]

        ### Prediccion:

            # Si x_new cae en r13

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] < s_star_vector[1]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r13


            # Si x_new cae en r23


            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] >= s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] >= s_star_vector[1]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r23



            # Si x_new cae en r33

            if (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] < s_star_vector[2]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2] ] < s_star_vector[2]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r33

            
            # Si x_new cae en r43

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] >= s_star_vector[2])  :

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2] ] >= s_star_vector[2]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r43

    
    if number_iterations == 4 :

            obs_r14 = obs_ramas[0]
            obs_r24 = obs_ramas[1]
            obs_r34 = obs_ramas[2]
            obs_r44 = obs_ramas[3]
            obs_r54 = obs_ramas[4]


         ### Prediccion:

            # Si x_new cae en r14

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] < s_star_vector[1]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r14


            # Si x_new cae en r24


            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) & (x_new[j_star_vector[3] - 1] >= s_star_vector[3]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3] ] >= s_star_vector[3]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r24



            # Si x_new cae en r34

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] >= s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1] ] >= s_star_vector[1]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r34

            
            # Si x_new cae en r44

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] < s_star_vector[2])  :

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2] ] < s_star_vector[2]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r44

            
            # Si x_new cae en r54

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] >= s_star_vector[2])  :

                y_new_predict = Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2] ] >= s_star_vector[2]) , 'Y' ]

                y_new_predict = y_new_predict.sum() / obs_r54

        


        
    return(y_new_predict)

Testeo del algoritmo regression tree ¶

In [ ]:
import pandas as pd
import numpy as np
import math
In [ ]:
House_Prices_Data = pd.read_csv('House_Price_Regression.csv')

Seleccionamos las variables con las que vamos a trabajar:

In [ ]:
House_Prices_Data = House_Prices_Data.loc[:, ['price', 'size_in_m_2', 'no_of_bedrooms', 'no_of_bathrooms', 'quality_recode', 'latitude', 'private_garden_recode', 'private_pool_recode', 'longitude']]
In [ ]:
House_Prices_Data.head()
Out[ ]:
price size_in_m_2 no_of_bedrooms no_of_bathrooms quality_recode latitude private_garden_recode private_pool_recode longitude
0 2700000 100.242337 1 2 2.0 25.113208 0.0 0.0 55.138932
1 2850000 146.972546 2 2 2.0 25.106809 0.0 0.0 55.151201
2 1150000 181.253753 3 5 2.0 25.063302 0.0 0.0 55.137728
3 2850000 187.664060 2 3 1.0 25.227295 0.0 0.0 55.341761
4 1729200 47.101821 0 1 2.0 25.114275 0.0 0.0 55.139764

Vemos la estructura de las columnas en Python (su type)

In [ ]:
House_Prices_Data.dtypes
Out[ ]:
price                      int64
size_in_m_2              float64
no_of_bedrooms             int64
no_of_bathrooms            int64
quality_recode           float64
latitude                 float64
private_garden_recode    float64
private_pool_recode      float64
longitude                float64
dtype: object

Transformaciones necesarias para poder aplicar sobre este data-set nuestro algoritmo:

  • Tranformar las variables categoricas a type=Object en Python
  • Llamar 'Y' a la variable respuesta (y hacer que sea la primera columna del data-set)
In [ ]:
House_Prices_Data['quality_recode'] = House_Prices_Data['quality_recode'].astype('object')
House_Prices_Data['private_garden_recode'] = House_Prices_Data['private_garden_recode'].astype('object')
House_Prices_Data['private_pool_recode'] = House_Prices_Data['private_pool_recode'].astype('object')

House_Prices_Data = House_Prices_Data.rename({'price': 'Y'}, axis=1)
In [ ]:
House_Prices_Data.dtypes
Out[ ]:
Y                          int64
size_in_m_2              float64
no_of_bedrooms             int64
no_of_bathrooms            int64
quality_recode            object
latitude                 float64
private_garden_recode     object
private_pool_recode       object
longitude                float64
dtype: object

Ahora dividimos el data-set en train y test

In [ ]:
House_Prices_Data_Train = House_Prices_Data.sample(frac=0.8, replace=False, weights=None, random_state=222, axis=None, ignore_index=False)

House_Prices_Data_Test = House_Prices_Data.drop( House_Prices_Data_Train.index , )
In [ ]:
House_Prices_Data_Train
Out[ ]:
Y size_in_m_2 no_of_bedrooms no_of_bathrooms quality_recode latitude private_garden_recode private_pool_recode longitude
925 3195000 233.558142 3 4 2.0 25.083483 0.0 0.0 55.148688
1502 430000 43.478604 0 1 2.0 25.065872 0.0 0.0 55.232983
867 3499900 221.016237 3 3 2.0 25.191285 0.0 0.0 55.275202
746 8000000 240.340061 3 4 2.0 25.083858 0.0 0.0 55.138714
729 635356 58.435987 1 2 3.0 25.046296 0.0 0.0 55.200783
... ... ... ... ... ... ... ... ... ...
131 2175000 128.670655 2 3 1.0 25.073593 0.0 0.0 55.137516
1324 2300000 127.277110 2 3 0.0 25.072573 0.0 1.0 55.131009
1391 1396000 78.874647 1 2 2.0 25.079895 0.0 0.0 55.134126
1191 3100000 185.341485 3 5 2.0 25.191719 0.0 0.0 55.270677
879 835000 82.683670 1 2 2.0 25.049772 0.0 0.0 55.204243

1524 rows × 9 columns

In [ ]:
## TEST

X_test = House_Prices_Data_Test.loc[: , House_Prices_Data_Test.columns != 'Y']
Y_test = House_Prices_Data_Test.loc[: , 'Y']

Data_Test = pd.concat([Y_test , X_test], axis=1)

##################################################################################################

## TRAIN

X_train = House_Prices_Data_Train.loc[: , House_Prices_Data_Train.columns != 'Y']
Y_train = House_Prices_Data_Train.loc[: , 'Y']

Data_Train = pd.concat([Y_train , X_train], axis=1)
In [ ]:
number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas  = regression_tree(Data_set=Data_Train  , iterations_vector=range(1,5), k=20)
El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo 20 de observaciones por rama
In [ ]:
j_star_vector
Out[ ]:
[1, 1, 1]
In [ ]:
s_star_vector
Out[ ]:
[424.102195, 238.20329199999998, 682.372535]
In [ ]:
RSS_star_vector
Out[ ]:
[5614108748385613.0, 2690546340191228.0, 875322463887715.8]
In [ ]:
obs_ramas
Out[ ]:
[1410, 87, 24, 3]

Validacion Simple con funcion de validación propia y funcion Regresssion Tree propia¶

In [ ]:
def Simple_Validation_Regression(Data_Test, X_train, Y_train, Y_test) :

    ##########################

    from joblib import Parallel, delayed
    import multiprocessing

    n_jobs  = multiprocessing.cpu_count()

    ##########################

    number_iterations, j_star_vector, s_star_vector, RSS_star_vector, obs_ramas  = regression_tree(Data_set=Data_Train  , iterations_vector=range(1,5), k=20)

    ##########################

    def prediction(i, Data_Test, X_train, Y_train ):

     x_new = Data_Test.iloc[ i , range(1, Data_Test.shape[1])]

     y_new_predict = regression_tree_PREDICTIONS(Data_Test, number_iterations, j_star_vector, s_star_vector, obs_ramas, x_new)
  
     return(y_new_predict)

    ##########################

    y_predictions_vector = []

    # Paralelizamos el siguiente bucle for :

    # for i in  range(0, len(Data_Test)):

        # y_new_predict = prediction(i, Data_Test, X_train, Y_train )

        # y_predictions_vector.append( y_new_predict )

    
    y_predictions_vector = Parallel(n_jobs=n_jobs)( delayed(prediction)( i, Data_Test, X_train, Y_train) for i in range(0, len(Data_Test)) )

    #########################

 
    ECM = sum( (y_predictions_vector - Y_test)**2 )/len(Y_test)     

 
    return(y_predictions_vector , ECM)
In [ ]:
y_predictions_vector , ECM_regression_tree_own_function = Simple_Validation_Regression(Data_Test, X_train, Y_train, Y_test) 
El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo 20 de observaciones por rama
In [ ]:
ECM_regression_tree_own_function
Out[ ]:
6931670996001.736

Comparando con regresion lineal:

In [ ]:
import statsmodels.formula.api as smf
In [ ]:
RLM = smf.ols(formula = 'Y ~ size_in_m_2 + no_of_bedrooms +	no_of_bathrooms + quality_recode + latitude + private_garden_recode + private_pool_recode + longitude', data = Data_Train)

RLM = RLM.fit() 
In [ ]:
ECM_lineal_regression = sum( ( RLM.predict(Data_Test) - Y_test)**2 ) 
In [ ]:
ECM_lineal_regression
Out[ ]:
747411022399145.0

Comparando con KNN:

In [ ]:
import sklearn

from sklearn.neighbors import NearestNeighbors
In [ ]:
def Simple_Validation_Regression(Data_Test, X_train, Y_train, Y_test) :

    ##########################

    from joblib import Parallel, delayed
    import multiprocessing

    n_jobs  = multiprocessing.cpu_count()

    ##########################

    knn_regression = sklearn.neighbors.KNeighborsRegressor(n_neighbors=10,  weights='uniform', p=2, metric='minkowski')

    ##########################

    def prediction(i, Data_Test, X_train, Y_train ):

     x_new = Data_Test.iloc[ i , range(1, Data_Test.shape[1])]

     knn_regression.fit(X_train, Y_train)
     
     y_new_predict = knn_regression.predict( [x_new] )

     return(y_new_predict)

    ##########################

    y_predictions_vector = []

    # Paralelizamos el siguiente bucle for :

    # for i in  range(0, len(Data_Test)):

        # y_new_predict = prediction(i, Data_Test, X_train, Y_train )

        # y_predictions_vector.append( y_new_predict )

    
    y_predictions_vector = Parallel(n_jobs=n_jobs)( delayed(prediction)( i, Data_Test, X_train, Y_train) for i in range(0, len(Data_Test)) )

    #########################

    from itertools import chain

    y_predictions_vector = list(chain(*y_predictions_vector))

    ECM = sum( (Y_test - y_predictions_vector)**2 )/len(Y_test)     

 
    return(y_predictions_vector , ECM)
In [ ]:
y_predictions_vector , ECM_KNN_regression = Simple_Validation_Regression(Data_Test, X_train, Y_train, Y_test)
In [ ]:
ECM_KNN_regression
Out[ ]:
1843698368841.3533

Comparación final:

In [ ]:
[ ECM_regression_tree_own_function , ECM_lineal_regression, ECM_KNN_regression]
Out[ ]:
[6931670996001.736, 747411022399145.0, 1843698368841.3533]
In [ ]:
ECM_KNN_regression < ECM_lineal_regression
Out[ ]:
True
In [ ]:
ECM_regression_tree_own_function < ECM_lineal_regression
Out[ ]:
True
In [ ]:
ECM_KNN_regression < ECM_regression_tree_own_function
Out[ ]:
True

Mejores modelos de regresión segun esta validacion simple:

  1. KNN para regresion
  2. Arbol de regresion (basado en nuestra funcion)
  3. Regresion lineal

Regression Trees in Sklearn ¶

sklearn.tree.DecisionTreeRegressor(*, criterion='squared_error', splitter='best', max_depth=None, min_samples_split=2, min_samples_leaf=1, min_weight_fraction_leaf=0.0, max_features=None, random_state=None, max_leaf_nodes=None, min_impurity_decrease=0.0, ccp_alpha=0.0)[source]¶

criterion{“squared_error”, “friedman_mse”, “absolute_error”, “poisson”}, default=”squared_error” The function to measure the quality of a split. Supported criteria are “squared_error” for the mean squared error, which is equal to variance reduction as feature selection criterion and minimizes the L2 loss using the mean of each terminal node, “friedman_mse”, which uses mean squared error with Friedman’s improvement score for potential splits, “absolute_error” for the mean absolute error, which minimizes the L1 loss using the median of each terminal node, and “poisson” which uses reduction in Poisson deviance to find splits.

splitter{“best”, “random”}, default=”best” The strategy used to choose the split at each node. Supported strategies are “best” to choose the best split and “random” to choose the best random split.

max_depthint, default=None Es la profundidad maxima del arbol (la distancia maxima entre el nodo raiz y alguno de los nodos terminales)

min_samples_split int or float, default=2

Es el numero minimo de observaciones que tienen que caer en un nodo para separarlo/dividirlo (split) en dos nuesvos cuadrados/nodos. Si en cierto nodo caen menos de min_samples_split observaciones, el algoritmo ya no lo dividirá.

If int, then consider min_samples_split as the minimum number.

If float, then min_samples_split is a fraction and ceil(min_samples_split * n_samples) are the minimum number of samples for each split.

min_samples_leaf es el numero minimo de observaciones que tienen que caer en cada rama del arbol. Si en una rama caen menos de min_samples_leaf observaciones, el algortimo se detiene. Un punto de corte (split point) y una variable sera solo considera para splitar un nodo si el numero de observaciones que quedarian en cada una de las dos nuevas ramas generadas tras la division es mayor que min_samples_leaf.

ccp_alphanon-negative float, default=0.0 Complexity parameter used for Minimal Cost-Complexity Pruning. The subtree with the largest cost complexity that is smaller than ccp_alpha will be chosen. By default, no pruning is performed. See Minimal Cost-Complexity Pruning for details

Ver mas en https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html?highlight=decision+tree

In [ ]:
import sklearn

from sklearn.tree import DecisionTreeRegressor
In [ ]:
x_new = X_test.iloc[ 5 , :]
In [ ]:
x_new
Out[ ]:
size_in_m_2                83.6127
no_of_bedrooms                   1
no_of_bathrooms                  2
quality_recode                 2.0
latitude                 25.204631
private_garden_recode          0.0
private_pool_recode            0.0
longitude                55.343457
Name: 38, dtype: object
In [ ]:
Regression_Tree_sklearn =  sklearn.tree.DecisionTreeRegressor(criterion='squared_error', splitter='best', min_samples_split=40, min_samples_leaf=100,  max_depth=None,  ccp_alpha=0, random_state=222)
In [ ]:
Regression_Tree_sklearn.fit(X_train, Y_train)
Out[ ]:
DecisionTreeRegressor(ccp_alpha=0, min_samples_leaf=100, min_samples_split=40,
                      random_state=222)

Predecir la respuesta para un vector de predictores :

In [ ]:
Regression_Tree_sklearn.predict( [x_new] ) 
Out[ ]:
array([1260448.41284404])

Obtener la profundidad del arbol generado :

In [ ]:
Regression_Tree_sklearn.get_depth()
Out[ ]:
6

Obtener el numero de ramas del arbol generado:

In [ ]:
Regression_Tree_sklearn.get_n_leaves()
Out[ ]:
13

nº de iteraciones (cudrados que se han separado en otros dos cuadrados) = nº ramas - 1

Plotear el arbol :

In [ ]:
from sklearn import tree
In [ ]:
fit = Regression_Tree_sklearn.fit(X_train, Y_train)
In [ ]:
tree.plot_tree( fit )
Out[ ]:
[Text(0.6, 0.875, 'X[0] <= 212.098\nsquared_error = 8925110924992.428\nsamples = 1524\nvalue = 2104623.691'),
 Text(0.4, 0.625, 'X[0] <= 94.157\nsquared_error = 957905433032.399\nsamples = 1372\nvalue = 1528312.921'),
 Text(0.2, 0.375, 'squared_error = 188191145861.077\nsamples = 572\nvalue = 887164.308'),
 Text(0.6, 0.375, 'X[4] <= 25.194\nsquared_error = 1004184944595.144\nsamples = 800\nvalue = 1986734.179'),
 Text(0.4, 0.125, 'squared_error = 623006716122.99\nsamples = 623\nvalue = 1770914.693'),
 Text(0.8, 0.125, 'squared_error = 1604855383739.994\nsamples = 177\nvalue = 2746369.994'),
 Text(0.8, 0.625, 'squared_error = 50781257227076.52\nsamples = 152\nvalue = 7306586.697')]
In [ ]:
pip install graphviz
Requirement already satisfied: graphviz in c:\users\usuario\appdata\local\programs\python\python310\lib\site-packages (0.20.1)
Note: you may need to restart the kernel to use updated packages.
In [ ]:
import graphviz 
In [ ]:
import os
os.environ["PATH"] += os.pathsep + 'C:/Users/Usuario/Downloads/windows_10_msbuild_Release_graphviz-6.0.1-win32/Graphviz/bin'
In [ ]:
dot_data = tree.export_graphviz( fit , out_file=None) 
graph = graphviz.Source(dot_data) 
graph.render("plot") 
Out[ ]:
'plot.pdf'
In [ ]:
dot_data = tree.export_graphviz(fit, out_file=None, 
                     feature_names=X_train.columns,  
                     filled=True, rounded=True,  
                      special_characters=True)  
graph = graphviz.Source(dot_data)  
graph 
Out[ ]:
b'\n\nTree\n\n\n\n0\n\nsize_in_m_2 \xe2\x89\xa4 243.963\nsquared_error = 8925110924992.428\nsamples = 1524\nvalue = 2104623.691\n\n\n\n1\n\nsize_in_m_2 \xe2\x89\xa4 136.985\nsquared_error = 1095658580360.871\nsamples = 1419\nvalue = 1583456.654\n\n\n\n0->1\n\n\nTrue\n\n\n\n24\n\nsquared_error = 61457213441282.64\nsamples = 105\nvalue = 9147823.933\n\n\n\n0->24\n\n\nFalse\n\n\n\n2\n\nsize_in_m_2 \xe2\x89\xa4 90.348\nsquared_error = 420740336742.606\nsamples = 977\nvalue = 1189615.95\n\n\n\n1->2\n\n\n\n\n\n17\n\nlatitude \xe2\x89\xa4 25.194\nsquared_error = 1486790960835.947\nsamples = 442\nvalue = 2454004.998\n\n\n\n1->17\n\n\n\n\n\n3\n\nlatitude \xe2\x89\xa4 25.072\nsquared_error = 175545698326.283\nsamples = 535\nvalue = 860543.316\n\n\n\n2->3\n\n\n\n\n\n12\n\nlatitude \xe2\x89\xa4 25.113\nsquared_error = 427799788104.803\nsamples = 442\nvalue = 1587927.848\n\n\n\n2->12\n\n\n\n\n\n4\n\nsize_in_m_2 \xe2\x89\xa4 67.912\nsquared_error = 26507223354.647\nsamples = 217\nvalue = 582042.59\n\n\n\n3->4\n\n\n\n\n\n7\n\nsize_in_m_2 \xe2\x89\xa4 66.519\nsquared_error = 188202561599.745\nsamples = 318\nvalue = 1050589.409\n\n\n\n3->7\n\n\n\n\n\n5\n\nsquared_error = 25018037599.38\nsamples = 100\nvalue = 504421.14\n\n\n\n4->5\n\n\n\n\n\n6\n\nsquared_error = 18228973055.146\nsamples = 117\nvalue = 648385.709\n\n\n\n4->6\n\n\n\n\n\n8\n\nsquared_error = 119596850033.824\nsamples = 109\nvalue = 819850.44\n\n\n\n7->8\n\n\n\n\n\n9\n\nlatitude \xe2\x89\xa4 25.125\nsquared_error = 181734886640.701\nsamples = 209\nvalue = 1170926.957\n\n\n\n7->9\n\n\n\n\n\n10\n\nsquared_error = 150429482794.485\nsamples = 100\nvalue = 1073348.57\n\n\n\n9->10\n\n\n\n\n\n11\n\nsquared_error = 193705990296.829\nsamples = 109\nvalue = 1260448.413\n\n\n\n9->11\n\n\n\n\n\n13\n\nlongitude \xe2\x89\xa4 55.171\nsquared_error = 294314305612.59\nsamples = 267\nvalue = 1363064.39\n\n\n\n12->13\n\n\n\n\n\n16\n\nsquared_error = 436612830119.76\nsamples = 175\nvalue = 1931005.24\n\n\n\n12->16\n\n\n\n\n\n14\n\nsquared_error = 283242762927.142\nsamples = 163\nvalue = 1600965.245\n\n\n\n13->14\n\n\n\n\n\n15\n\nsquared_error = 83934748372.171\nsamples = 104\nvalue = 990200.548\n\n\n\n13->15\n\n\n\n\n\n18\n\nlongitude \xe2\x89\xa4 55.142\nsquared_error = 1026408472260.744\nsamples = 338\nvalue = 2159356.231\n\n\n\n17->18\n\n\n\n\n\n23\n\nsquared_error = 1783861861918.73\nsamples = 104\nvalue = 3411613.49\n\n\n\n17->23\n\n\n\n\n\n19\n\nsquared_error = 1625610241024.812\nsamples = 107\nvalue = 2647677.907\n\n\n\n18->19\n\n\n\n\n\n20\n\nsize_in_m_2 \xe2\x89\xa4 157.471\nsquared_error = 587238586362.706\nsamples = 231\nvalue = 1933163.939\n\n\n\n18->20\n\n\n\n\n\n21\n\nsquared_error = 366141829321.83\nsamples = 101\nvalue = 1703999.248\n\n\n\n20->21\n\n\n\n\n\n22\n\nsquared_error = 686513082517.878\nsamples = 130\nvalue = 2111207.277\n\n\n\n20->22\n\n\n\n\n\n'

Validación simple con función de validacion propia y funcion Regression Tree de sklearn¶

In [ ]:
def Simple_Validation_Regression(Data_Test, X_train, Y_train, Y_test) :

    ##########################

    from joblib import Parallel, delayed
    import multiprocessing

    n_jobs  = multiprocessing.cpu_count()

    ##########################

    Regression_Tree_sklearn =  sklearn.tree.DecisionTreeRegressor(criterion='squared_error', splitter='best', max_depth=None,  ccp_alpha=0.0,  random_state=222)

    ##########################

    def prediction(i, Data_Test, X_train, Y_train ):

     x_new = Data_Test.iloc[ i , range(1, Data_Test.shape[1])]

     Regression_Tree_sklearn.fit(X_train, Y_train)

     y_new_predict = Regression_Tree_sklearn.predict( [x_new] ) 
  
     return(y_new_predict)

    ##########################

    y_predictions_vector = []

    # Paralelizamos el siguiente bucle for :

    # for i in  range(0, len(Data_Test)):

        # y_new_predict = prediction(i, Data_Test, X_train, Y_train )

        # y_predictions_vector.append( y_new_predict )

    
    y_predictions_vector = Parallel(n_jobs=n_jobs)( delayed(prediction)( i, Data_Test, X_train, Y_train) for i in range(0, len(Data_Test)) )

    #########################

    from itertools import chain

    y_predictions_vector = list(chain(*y_predictions_vector))

 
    ECM = sum( (y_predictions_vector - Y_test)**2 )/len(Y_test)     

 
    return(y_predictions_vector , ECM)
In [ ]:
y_predictions_vector , ECM_regression_tree_sklearn = Simple_Validation_Regression(Data_Test, X_train, Y_train, Y_test)
In [ ]:
ECM_regression_tree_sklearn
Out[ ]:
1063732269951.5052

Comparaciones:

In [ ]:
[ ECM_regression_tree_sklearn, ECM_regression_tree_own_function , ECM_KNN_regression, ECM_lineal_regression  ]
Out[ ]:
[1063732269951.5052, 6931670996001.736, 1843698368841.3533, 747411022399145.0]
In [ ]:
ECM_regression_tree_sklearn < ECM_regression_tree_own_function
Out[ ]:
True
In [ ]:
ECM_regression_tree_sklearn < ECM_KNN_regression
Out[ ]:
True

Por tanto el ranking de mejores modelos segun esta validacion simple sería:

  1. Regression tree sklearn
  2. KNN
  3. Regression tree own function
  4. Linear Regression

Podar el arbol con arbol penalizado¶


Classification Trees ¶

La idea de los algoritmos de arboles de clasificacion es segmentar las observaciones de los predictores $X_1,...,X_p$ para predecir el valor de la respuesta $Y$ en base a esa informacion segmentada. Es algo asi como predecir Y por grupos/segmentos.

Definicion formal de los arboles de clasificación:¶

Elementos Básicos¶

  • Tenemos unos predictores $\hspace{0.1cm} X_1,...,X_p \hspace{0.1cm}$ y una variable respuesta categorica $\hspace{0.1cm} Y$
  • Tenemos un arbol $\hspace{0.1cm} T \hspace{0.1cm}$ de la forma del expuesto en la imagen con $\hspace{0.1cm} m-1 \hspace{0.1cm}$ iteraciones y $\hspace{0.1cm} m \hspace{0.1cm}$ ramas.
  • $r_{ht}$ es la rama $h$ del arbol con $t$ iteraciones.
  • Cada iteracion del arbol tiene asociado uno de los predictores $\hspace{0.07cm} X_1,...,X_n$
  • Cada iteracion del arbol tiene dos tallos (tallo 1 (izquierdo) y tallo 2 (derecho)).
  • En cada tallo de una iteracion se define un intervalo.

  • $\hspace{0.1cm} I_{lt} \hspace{0.1cm}$ es el intervalo asociado al tallo $l$ de la iteracion $\hspace{0.1cm} t$

  • Para simplificar el problema consideraremos $\hspace{0.1cm} I_{1t} = (-\infty \hspace{0.03cm},\hspace{0.03cm} s_t)\hspace{0.1cm}$ y $\hspace{0.1cm} I_{2t} = [s_t \hspace{0.03cm},\hspace{0.03cm} \infty]\hspace{0.1cm}$ donde $\hspace{0.1cm} s_t \hspace{0.1cm}$ es llamado punto de corte de la iteracion $\hspace{0.1cm} t \hspace{0.1cm}$ del arbol
  • $R_{ht} \hspace{0.1cm}$ es la region (rectangulo $n$-dimensional) definida por la rama $\hspace{0.1cm} h \hspace{0.1cm}$ de un arbol con $t$ iteraciones

Criterio de prediccion de la variable respuesta¶

Dada una nueva observacion $\hspace{0.1cm} x_{new}= (x_{new,1},x_{new,2},...,x_{new,p} ) \hspace{0.1cm}$ la idea es predecir $\hspace{0.1cm} y_{new} \hspace{0.1cm}$ como sigue:

Sea $ \hspace{0.1 cm} f_{r, R_{ht}} \hspace{0.1 cm}$ la frecuencia relativa de la clase/grupo r en la rama $h$ de un arbol con $t$ iteraciones.

Es decir, es la proporcion de individuos de la muestra de entrenamiento que caen en la rama $h$ de un arbol con $t$ iteraciones que pertenecen a la clase $r$ (es decir, para los que $Y=r$ ) :

$$ \hspace{0.1 cm} f_{r , R_{ht}} \hspace{0.1 cm} = \hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{ht} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{ht} \rbrace} $$

Donde: $\hspace{0.25cm} r \in Rango(Y) = \lbrace 0,1,..,c-1 \rbrace $

$Si \hspace{0.3cm} x_{new} \in R_{ht} \hspace{0.12cm} \Rightarrow \hspace{0.12cm}$ $x_{new}$ es clasificado en la clase/grupo mayoritaria (mas frecuente) en la rama $h$ $(r_h)$

Por tanto:

$\hspace{0.4 cm} Si \hspace{0.22 cm} r_{R_{ht}}^* \hspace{0.05 cm}= \hspace{0.05 cm} \underset{\hspace{0.7 cm} r}{arg \hspace{0.1 cm} Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{ht}} \hspace{0.1 cm}\right) \hspace{0.2 cm} ,\hspace{0.05 cm} entonces:$

$$Si \hspace{0.3cm} x_{new} \in R_h \hspace{0.22cm} \Rightarrow \hspace{0.22cm} \widehat{y}_{new} = r_{R_{ht}}^*$$

Observacion:

Definida la region $\hspace{0.05 cm} R_{ht} \hspace{0.05 cm}$ , es relativamente sencillo resolver el problema $ \hspace{0.05 cm} \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{ht}} \hspace{0.1 cm}\right) \hspace{0.05 cm}$ y asi obtener $\hspace{0.05 cm} r_{R_{ht}}^*$


Objetivo : Usando la tasa de error de clasificacion como métrica a optimizar¶

Definimos el error de entrenamiento de la rama $h$ de un arbol de clasificacion con $t$ iteraciones como la tasa de error de clasificacion para las observaciones de entrenamiento que caen en la rama $h$ de dicho arbol, es decir, como:

$$TEC(R_{ht}) = 1 - f_{r^*_{R_{ht}} , R_{ht}}$$

Observación:

$f_{r^*_{R_{ht}} , R_{ht}}$ es la proporcion de individuos de la muestra de entrenamiento que caen en la rama $h$ de un arbol con $t$ iteraciones que son de la clase/grupo $r^*_{R_{ht}}$ (el valor de la variable respuesta para ellos es $r^*_{R_{ht}}$)

Como el modelo clasifica a los que caen en esa rama como de la clase $r^*_{R_{ht}}$ , es decir, como la predicion de la respuesta para todo individuo que pertenezaca a esa rama es $r^*_{R_{ht}}$ , por parte del modelo, entonces se tiene lo siguiente:

$f_{r^*_{R_{ht}} , R_{ht}}$ es la proporcion de individuos de la muestra de entrenamiento que caen en la rama $h$ de un arbol con $t$ iteraciones que son correctamente clasificados por el modelo (proporcion de individuos de la region $R_{ht}$ a los que se les ha predicho bien la respuesta).

$TEC(R_{ht})$ es la proporcion de individuos de la muestra de entrenamiento que caen en la rama $h$ de un arbol con $t$ iteraciones $($ sus observaciones de los predictores pertenecen a $R_{ht}$ $)$ y que han sido clasificados erroneamente. Se les ha clasificado en la clase $r^*_{R_{ht}}$ y su clase era otra diferente, es decir, tenian un valor distinto a $r^*_{R_{ht}}$ para la variable respeusta, que es el valor que el modelo les predice para la respuesta.


Definimos el error global de entrenamiento de un arbol de clasificación como la suma de los errores de entrenamiento de las ramas del arbol de clasificación:

$$\sum_{h=1}^{m} \hspace{0.1cm} TEC(R_h) $$

El objetivo es construir un arbol de regresion con $m$ ramas tal que minimice el error global de entrenamiento.

Es decir, formalmente el objetivo es:

$$ \underset{R_1,..,R_m}{Min} \hspace{0.12cm} \sum_{h=1}^{m} \hspace{0.1cm} TEC(R_h) $$

Pero para escoger las regiones $\hspace{0.1cm} R_1,...,R_m \hspace{0.1cm}$ que definen las ramas del arbol hay que determinar dos elementos que definen a su vez a las regiones:

$1.\hspace{0.1cm}$ Qué predictores estan asociados a cada iteracion del arbol $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ Para cada iteracion $i$ escoger $X_j \hspace{0.01cm}$ $(\hspace{0.01cm} $ es decir, escoger $j \hspace{0.01cm})$

$2.\hspace{0.1cm}$ Qué intervalos estan asociados a cada uno de los dos tallos de cada interaccion $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ Para cada iteracion $i$ escoger $I_{1i}$ y $I_{2i}\hspace{0.1cm}$ $(\hspace{0.01cm}$ es decir, escoger el punto de corte $\hspace{0.07cm}s_i \hspace{0.04cm} )$

Por tanto el porblema a resolver se puede reformular como:

Para cada iteracion $\hspace{0.1cm} i \hspace{0.1cm}$ escoger $\hspace{0.1cm} X_j\hspace{0.01cm}$ $(\hspace{0.05cm}$ es decir $\hspace{0.01cm}j \hspace{0.05cm})\hspace{0.05cm}$ y $\hspace{0.05cm}( I_{1i}\hspace{0.1cm},\hspace{0.1cm}I_{2i} )\hspace{0.1cm}$ $\hspace{0.1cm}($ es decir $\hspace{0.1cm} s_i)\hspace{0.1cm}$ tal que se acaben formando un arbol cuyas ramas definan unas regiones $\hspace{0.1cm}R_1,...,R_m\hspace{0.1cm}$ que minimicen $\hspace{0.1cm}\sum_{h=1}^{m} \hspace{0.1cm} TEC(R_h)$


Objetivo : Usando el índice de Gini como métrica a optimizar¶

Definimos el error de entrenamiento de la rama $h$ de un arbol de clasificacion con $t$ iteraciones como el índice de Gini de la respuesta en la rama $h$ del arbol con $t$ iteraciones (indice de gini de la respuesta en la region $R_{ht}$) , es decir, como:

$$ G_{R_{ht}} = \sum_{r=0,1,..,c-1}^{} f_{r , R_{ht}}\cdot(1 - f_{r , R_{ht}}) $$

Donde: $\hspace{0.15cm} Rango(Y) = \lbrace 0,1,...,c-1 \rbrace$

$G_{R_{ht}}$ toma valores pequeños cuando la frecuencia de una clase $r=0,1,...$ en la region $R_{ht}$ es alta , y por tanto la del resto baja.

$G_{R_{ht}}$ toma valores altos cuando las frecuencias de las clases se reparten de manera "igualitaria" en la region $R_{ht}$. Y cuanto mas igualitaria es la reparticion de las classes, mas alto es $G_{R_{ht}}$ . Hasta el punto que cuando la reparticion es totalmente igualitaria, esto es, cada clase tiene la misma frecuencia , si hay $c$ clases, cada una tiene una frecuencia relativa de $1/c$ en la region, entonces en indicide de Gini alcanza su maximo valor.

Ejemplo:

Para $\hspace{0.1 cm} c=3$ $\hspace{0.15cm} ( Rango(Y)=\lbrace 0,1,2 \rbrace )$

Si tenemos: $\hspace{0.15cm} f_{0 , R_{ht}} = 0.40 \hspace{0.15cm}$ , $\hspace{0.15cm} f_{1 , R_{ht}}=0.30 \hspace{0.15cm}$ y $\hspace{0.15cm} f_{2 , R_{ht}}=0.30$ $\hspace{0.15cm} \Rightarrow \hspace{0.15cm}$ $G_{R_{ht}} = 0.66 $

Si tenemos: $\hspace{0.15cm} f_{0 , R_{ht}} = 0.80 \hspace{0.15cm}$ , $\hspace{0.15cm} f_{1 , R_{ht}}=0.10 \hspace{0.15cm}$ y $\hspace{0.15cm} f_{2 , R_{ht}}=0.10$ $\hspace{0.15cm} \Rightarrow \hspace{0.15cm}$ $G_{R_{ht}} = 0.34 $

Si tenemos: $\hspace{0.15cm} f_{0 , R_{ht}} = 0.9 \hspace{0.15cm}$ , $\hspace{0.15cm} f_{1 , R_{ht}}=0.05 \hspace{0.15cm}$ y $\hspace{0.15cm} f_{2 , R_{ht}}=0.05$ $\hspace{0.15cm} \Rightarrow \hspace{0.15cm}$ $G_{R_{ht}} = 0.185 $

Teniendo esto en cuenta nos interesan que en cada rama (region $R_{ht}$) la frecuencia de la clase mayoritaria sea lo mayor posible, y eso equivale a que el indice de Gini sea lo menos posible dentro de cada rama, siguiendo la filosofia empleada con la $TEC$, donde nos interesaba que $f_{r^*_{R_{ht}} , R_{ht}}$ fuese lo mayor posible en cada rama.


Definimos el error global de entrenamiento de un arbol de clasificación como la suma de los errores de entrenamiento de las ramas del arbol de clasificación:

$$\sum_{h=1}^{m} \hspace{0.1cm} G_{R_{ht}} $$

El objetivo es construir un arbol de regresion con $m$ ramas tal que minimice el error global de entrenamiento.

Es decir, formalmente el objetivo es:

$$ \underset{R_1,..,R_m}{Min} \hspace{0.12cm} \sum_{h=1}^{m} \hspace{0.1cm} G_{R_{ht}} $$

En el fondo minimizar el error de clasificacion de un arbol de clasificacion equivale a minimizar el indice de Gini en las ramas del arbol conjuntamente (a nivel global).


Pero para escoger las regiones $\hspace{0.1cm} R_1,...,R_m \hspace{0.1cm}$ que definen las ramas del arbol hay que determinar dos elementos que definen a su vez a las regiones:

$1.\hspace{0.1cm}$ Qué predictores estan asociados a cada iteracion del arbol $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ Para cada iteracion $i$ escoger $X_j \hspace{0.01cm}$ $(\hspace{0.01cm} $ es decir, escoger $j \hspace{0.01cm})$

$2.\hspace{0.1cm}$ Qué intervalos estan asociados a cada uno de los dos tallos de cada interaccion $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ Para cada iteracion $i$ escoger $I_{1i}$ y $I_{2i}\hspace{0.1cm}$ $(\hspace{0.01cm}$ es decir, escoger el punto de corte $\hspace{0.07cm}s_i \hspace{0.04cm} )$

Por tanto el porblema a resolver se puede reformular como:

Para cada iteracion $\hspace{0.1cm} i \hspace{0.1cm}$ escoger $\hspace{0.1cm} X_j\hspace{0.01cm}$ $(\hspace{0.05cm}$ es decir $\hspace{0.01cm}j \hspace{0.05cm})\hspace{0.05cm}$ y $\hspace{0.05cm}( I_{1i}\hspace{0.1cm},\hspace{0.1cm}I_{2i} )\hspace{0.1cm}$ $\hspace{0.1cm}($ es decir $\hspace{0.1cm} s_i)\hspace{0.1cm}$ tal que se acaben formando un arbol cuyas ramas definan unas regiones $\hspace{0.1cm}R_1,...,R_m\hspace{0.1cm}$ que minimicen $\hspace{0.1cm}\sum_{h=1}^{m} \hspace{0.1cm} G_{R_{ht}}$


Algoritmo para la resolucion del problema $\hspace{0.1cm}\Rightarrow\hspace{0.1cm}$ Algoritmo de particion binaria ¶

El siguiente algoritmo es una forma de resolver el problema planteado anteriormente. Consiste en ir generando el arbol de manera secuencial, iteracion a iteracion, minimizando en cada paso el error de clasificacion para las observaciones de train que caen en las ramas asociadas a la iteracion en cuestion que esta siendo optimizada.

El algoritmo se basa en la resolucion secuencial de problemas de minimizacion, uno por cada iteracion tenga el arbol que se acabará generando.

Importante:

Para esta exposicion teorica del algoritmo se va a usar como metrica principal la TEC , pero es facilmente extrapolable al caso en el que se usase el índice de Gini como metrica a optimizar.


Problema de la Iteracion 1¶

Arbol con 1 iteracion:

In [ ]:
from IPython.display import Image
Image(filename='arbol 1iter.jpg', width = 600, height = 300) 
Out[ ]:

La idea es, determinar las regiones $R_{11}$ y $R_{21}\hspace{0.1cm}$ $($ es decir, $j$ y $s_1 \hspace{0.05cm}) \hspace{0.1cm}$ del arbol con 1 iteracion tal que minimizan el error de entrenamiento global de dicho arbol con 1 iteracion.


Mas formalmente el problema planteado es:

  • Si utilizamos la TEC como metrica de error a minimizar:
$$ \underset{R_{11} , R_{21}} {Min} \hspace{0.15cm} \left(\hspace{0.1cm} TEC_1 = TEC(R_{11}) + TEC(R_{21}) \hspace{0.1cm}\right) \hspace{0.1cm} = \\[15pt] =\hspace{0.2cm} \underset{R_{11} , R_{21}} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} \left( 1 - f_{r^*_{R_{11}} , R_{11}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{21}} , R_{21}} \right) \hspace{0.2cm} \right) \\[25pt] =\hspace{0.2cm} \underset{R_{11} , R_{21}} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{11}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \rbrace} \hspace{0.3cm} + \hspace{0.3cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{21}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \rbrace} \hspace{0.2cm} \right) \\[25pt] =\hspace{0.2cm} \underset{j , s_1} {Min} \hspace{0.1cm} \left( \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i < s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{11}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i < s_1 \rbrace} \hspace{0.3cm} + \hspace{0.3cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \geqslant s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{21}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \geqslant s_1 \rbrace} \hspace{0.2cm} \right) $$
  • Si utilizamos el índice de Gini como metrica de error a minimizar:
$$ \underset{R_{11} , R_{21}} {Min} \hspace{0.15cm} \left(\hspace{0.1cm} G_1 = G_{R_{11}} + G_{R_{21}} \hspace{0.1cm}\right) \hspace{0.1cm} = \\[15pt] =\hspace{0.2cm} \underset{R_{11} , R_{21}} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{11}}\cdot(1 - f_{r , R_{11}}) \hspace{0.1cm} + \hspace{0.1cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{21}}\cdot(1 - f_{r , R_{21}}) \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{R_{11} , R_{21}} {Min} \hspace{0.1cm} \Biggl\{\hspace{0.2cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \rbrace} \right) \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \rbrace} \right) \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{j , s_1} {Min} \hspace{0.1cm} \Biggl\{ \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} < s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} < s_1 \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} < s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} < s_1 \rbrace} \right) \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} \geqslant s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} \geqslant s_1 \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} \geqslant s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} \geqslant s_1 \rbrace} \right) \Biggl\} $$

Notar que:

$R_{11} = \lbrace (v_1 ,..., v_n) / v_j < s_1 \rbrace \hspace{0.3cm}\Rightarrow\hspace{0.3cm} [\hspace{0.1cm} x_i \in R_{11} \hspace{0.1cm} \Leftrightarrow \hspace{0.1cm} x_{ij} < s_1 \hspace{0.1cm}] \hspace{0.3cm}\Rightarrow\hspace{0.3cm} \lbrace i/x_i \in R_{11} \rbrace = \lbrace i / x_{ij} < s_1 \rbrace$

$ R_{12} = \lbrace (v_1 ,..., v_n) / v_j \geqslant s_1 \rbrace \hspace{0.3cm}\Rightarrow\hspace{0.3cm} [\hspace{0.1cm} x_i \in R_{21} \hspace{0.1cm} \Leftrightarrow \hspace{0.1cm} x_{ij} \geqslant s_1 \hspace{0.1cm}] \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \lbrace i/x_i \in R_{11} \rbrace = \lbrace i / x_{ij} \geqslant s_1 \rbrace$

Notese que determinar $R_{11}$ y $R_{21}$ es equivalente a determinar el predictor $X_j$ $($ es decir $j)$ y el punto de corte $s_1$ asociados a la Iteracion 1, ya que $R_{11}$ y $R_{21}$ quedan determinadas al fijar $X_j$ y $s_1$

Notar también que:

Fijado $(j, s_1)$ puede calcularse $r_{R_{11}}^*$ como solucion al problema de maximizacion:

$$\underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{11}} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{11} \rbrace} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} < s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} < s_1 \rbrace} \hspace{0.1 cm}\right) $$

Fijado $(j, s_2)$ puede calcularse $r_{R_{21}}^*$ como solucion al problema de maximizacion:

$$\underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{21}} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{21} \rbrace} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} \geqslant s_1 \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij} \geqslant s_1 \rbrace} \hspace{0.1 cm}\right) $$

Donde :

  • $\hspace{0.2cm} j \in \lbrace 1,2,...,p \rbrace $
  • Si $X_j$ es cuantitativa:

$\hspace{0.7cm}$ Ordenamos las observaciones de $X_j$ y quitamos repeticiones, obtenemos $X_j^{order}$, entonces:

$$ s_1 \in \Biggl\{ \dfrac{ x_{(1)j} + x_{(2)j} }{2} \hspace{0.1cm}, \hspace{0.1cm} \dfrac{x_{(2)j} + x_{(3)j} }{2} \hspace{0.1cm} ,...,\hspace{0.1cm} \dfrac{x_{(n-1)j} + x_{(n)j} }{2} \Biggl\}$$

Donde $\hspace{0.1cm} x_{(i)j} \hspace{0.1cm} $ es la observacion que ocupa la posicion $i$-esima en $\hspace{0.1cm} X_j^{order}$

  • Si $X_j$ es categorica con $c$ categorias:
$$ s_1 \in Rango(X_j) = \lbrace 0,1,..., c-1 \rbrace $$

Notese que la eleccion de $X_j$ determina el campo de variacion de $s_1$

  • $TEC(R_{11})$ es el error de entrenamiento de la rama $1$ de un arbol de clasificación con 1 iteracion

  • $TEC(R_{21})$ es el error de entrenamiento de la rama $2$ de un arbol de clasificación con 1 iteracion

Estos elementos no volveran a ser definidos en los sucesivos problemas de iteracion para no pecar de ser repetitivo, puesto que pueden ser facilmente extrapolados a cualquier problema de iteracion. Ademas las definiciones generales de estos elementos han sido expuestas ya anteriormente.

  • Denotaremos por $\hspace{0.1cm} \left(\hspace{0.1cm} j^{*(i)} \hspace{0.05cm},\hspace{0.05cm} s^{*(i)} \hspace{0.1cm}\right) \hspace{0.1cm}$ a una solucion del problema de la Iteracion $i$ , para $i=1,...,m-1$

Arbol obtenido tras resolver el problema de la Iteracion 1:

In [ ]:
from IPython.display import Image
Image(filename='iter1.jpg', width = 600, height = 300) 
Out[ ]:
  • Si alguna de las ramas del arbol resultante de resolver el problema la iteracion 1 tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2

Notese que $k$ será un *hiperparametro* del algoritmo.


Problema de la Iteracion 2¶

Arbol con 2 iteraciones tras resolver el problema anterior:

In [ ]:
from IPython.display import Image
Image(filename='arbol 2iter.jpg', width = 600, height = 300) 
Out[ ]:

Si estamos en este problema es porque ninguna rama del arbol resultante del problema de la Iteracion 1 tiene menos de $k$ observaciones

La idea es, determinar las regiones $R_{12}$ , $R_{22}$ y $R_{32}$ del arbol con 2 iteraciones (es decir, $j$ y $s_2$), considerando la solucion del problema de la iteracion 1 (arbol de arriba) , que minimizan el error de entrenamiento global de dicho arbol.

Notese que $R_{32}$ ya esta determinada tras la resolucion del problema anterior, por ello realmente solo hay que determinar las regiones $R_{12}$ y $R_{22}$ óptimas (a saber, $j$ y $s_2$ óptimos)

Mas formalmente el problema planteado es:

  • Si utilizamos la TEC como metrica de error a minimizar:
$$ \underset{R_{12} , R_{22}, R_{32}} {Min} \hspace{0.15cm} \Biggl\{ \hspace{0.1cm} TEC_2 = TEC(R_{12}) + TEC(R_{22}) + TEC(R_{32}) \hspace{0.1cm} \Biggl\} \hspace{0.1cm} = \\[25pt] =\hspace{0.2cm} \underset{R_{12} , R_{22}, R_{32}} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} \left( 1 - f_{r^*_{R_{12}} , R_{12}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{22}} , R_{22}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{32}} , R_{32}} \right) \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_2} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{12}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \rbrace} \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{22}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \rbrace} \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{32} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{32}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{32} \rbrace} \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_2} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{12}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{22}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \hspace{0.3cm} + \hspace{0.1cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \geqslant s^{*(1)} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{32}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \geqslant s^{*(1)} \rbrace} \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_2} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{12}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{22}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \hspace{0.2cm} \Biggl\} \\[35pt] =\hspace{0.2cm} \underset{R_{12} , R_{22} } {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} \left( 1 - f_{r^*_{R_{12}} , R_{12}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{22}} , R_{22}} \right) \hspace{0.2cm} \Biggl\} $$
  • Si utilizamos el índice de Gini como metrica de error a minimizar:
$$ \underset{R_{12} , R_{22}, R_{32}} {Min} \hspace{0.15cm} \Biggl\{ \hspace{0.1cm} G_1 = G_{R_{12}} + G_{R_{22}} + G_{R_{32}} \hspace{0.1cm} \Biggl\} \hspace{0.1cm} = \\[15pt] =\hspace{0.2cm} \underset{R_{12} , R_{22}, R_{32}} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{12}}\cdot(1 - f_{r , R_{12}}) \hspace{0.1cm} + \hspace{0.1cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{22}}\cdot(1 - f_{r , R_{22}}) \hspace{0.1cm} + \hspace{0.1cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{32}}\cdot(1 - f_{r , R_{32}}) \hspace{0.3cm} \Biggl\} \\[35pt] =\hspace{0.2cm} \underset{R_{12} , R_{22} , R_{32}} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \rbrace} \right) \\[25pt] \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \rbrace} \right) \\[20pt] \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{32} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{32} \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{32} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{32} \rbrace} \right) \hspace{0.3cm} \Biggl\} \\[35pt] = \hspace{0.2cm} \underset{j , s_2} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \right) \\[25pt] \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \right) \\[25pt] \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \geqslant s^{*(1)} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \geqslant s^{*(1)} \rbrace} \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \geqslant s^{*(1)} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \geqslant s^{*(1)} \rbrace} \right) \hspace{0.3cm} \Biggl\} \\[35pt] $$$$ = \hspace{0.2cm} \underset{j , s_2} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \right) \\[25pt] \hspace{0.3cm} + \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \cdot \left( 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \right) \Biggl\} \\[25pt] = \hspace{0.2cm} \underset{R_{12} , R_{22} } {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.3cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{12}}\cdot(1 - f_{r , R_{12}}) \hspace{0.1cm} + \hspace{0.1cm} \sum_{r=0,1,..,c-1}^{} f_{r , R_{22}}\cdot(1 - f_{r , R_{22}}) \hspace{0.3cm} \Biggl\} $$

Notar que:

Fijado $(j, s_2)$ puede calcularse $r_{R_{12}}^*$ como solucion al problema de maximizacion:

$$\underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{12}} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \rbrace} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace }\right) $$

Fijado $(j, s_2)$ puede calcularse $r_{R_{22}}^*$ como solucion al problema de maximizacion:

$$\underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{22}} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{22} \rbrace} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_2 \hspace{0.1 cm} \rbrace } \right) $$

Notese que ninguna de las siguientes expresiones:

$$ \left( 1 - f_{r^*_{R_{32}} , R_{32}} \right) $$

$$ \sum_{r=0,1,..,c-1}^{} f_{r , R_{32}}\cdot(1 - f_{r , R_{32}})$$

dependen de $(j, s_2)$ , por lo que puede sacarse de la funcion objetivo de sus respectivos problemas de minimizacion sin que esto altere la solucion del problema.

Arbol tras resolver el problema de la Iteracion 2:

In [ ]:
from IPython.display import Image
Image(filename='iter2.jpg', width = 940, height = 320)
Out[ ]:
  • Si alguna de las ramas tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2


*Problema de la Iteracion 3:*

Arbol con 3 iteraciones tras resolver el problema anterior:

In [ ]:
from IPython.display import Image
Image(filename='arbol 3iter.jpg', width = 940, height = 320)
Out[ ]:

Si estamos en este problema es porque ninguna rama del arbol resultante del problema de la Iteracion 2 tiene menos de $k$ observaciones

La idea es, determinar las regiones $R_{13}$ , $R_{23}$, $R_{33}$ y $R_{43}$ del arbol con 3 iteraciones $($ es decir, $j$ y $s_3 \hspace{0.05cm})$, considerando la solucion del problema de la iteracion 2 (arbol de arriba), que minimizan el error de entrenamiento global de dicho arbol.

Notese que $R_{13}$ y $R_{23}$ ya están determinadas tras la resolucion del problema anterior, por ello realmente solo hay que determinar las regiones $R_{33}$ y $R_{43}$ óptimas (a saber, $j$ y $s_3$ óptimos)


Mas formalmente el problema se plantea como sigue:

$$ \underset{R_{13} , R_{23}, R_{33}, R_{43}} {Min} \hspace{0.15cm} \Biggl\{\hspace{0.1cm} TEC_3 = TEC(R_{13}) + TEC(R_{23}) + TEC(R_{33}) + TEC(R_{43}) \hspace{0.1cm} \Biggl\} \hspace{0.1cm} = \\[25pt] =\hspace{0.2cm} \underset{R_{13} , R_{23}, R_{33}, R_{43}} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} \left( 1 - f_{r^*_{R_{13}} , R_{13}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{23}} , R_{23}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{33}} , R_{33}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{43}} , R_{43}} \right) \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_3} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{13} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{13}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{12} \rbrace} \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{23} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{23}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{23} \rbrace} \hspace{0.4cm} + \hspace{0.4cm} \\[35pt] 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{33} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{33}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{33} \rbrace} \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{43} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r^*_{R_{43}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{43} \rbrace} \hspace{0.2cm} \Biggl\} \\[35pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_3} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij^{*(2)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{13}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s^{*(2)} \hspace{0.1 cm} \rbrace } \hspace{0.4cm} + \hspace{0.4cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(2)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{23}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(2)} \hspace{0.1 cm} \rbrace } \hspace{0.3cm} + \hspace{0.1cm} \\[35pt] \hspace{1cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{33}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 \hspace{0.1 cm} \rbrace } \hspace{0.2cm} \hspace{0.3cm} + \hspace{0.3cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{43}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 \hspace{0.1 cm} \rbrace } \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_3} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{33}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 \hspace{0.1 cm} \rbrace } \hspace{0.3cm} + \hspace{0.3cm} 1 - \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r^*_{R_{43}} \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} < \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 \hspace{0.1 cm} \rbrace } \hspace{0.2cm} \Biggl\} \\[35pt] =\hspace{0.2cm} \underset{j \hspace{0.02cm},\hspace{0.02cm} s_3} {Min} \hspace{0.1cm} \Biggl\{ \hspace{0.2cm} \left( 1 - f_{r^*_{R_{33}} , R_{33}} \right) \hspace{0.3cm} + \hspace{0.1cm} \left( 1 - f_{r^*_{R_{43}} , R_{43}} \right) \hspace{0.2cm} \Biggl\} \\[25pt] =\hspace{0.2cm} \underset{ R_{33}, R_{43}} {Min} \hspace{0.15cm} \Biggl\{\hspace{0.1cm} TEC(R_{33}) + TEC(R_{43}) \hspace{0.1cm} \Biggl\} \hspace{0.1cm} $$

Notar que:

Fijado $(j, s_3)$ puede calcularse $r_{R_{33}}^*$ como solucion al problema de maximizacion:

$$\underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{33}} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{33} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{33} \rbrace} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} < \hspace{0.05cm} s_3 \hspace{0.1 cm} \rbrace }\right) $$

Fijado $(j, s_3)$ puede calcularse $r_{R_{43}}^*$ como solucion al problema de maximizacion:

$$\underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} f_{r, R_{43}} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{43} \hspace{0.15 cm}\text{y}\hspace{0.15 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_i \in R_{43} \rbrace} \hspace{0.1 cm}\right) = \underset{ r}{ Max} \hspace{0.05 cm} \left(\hspace{0.1 cm} \dfrac{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm}/\hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 \hspace{0.25 cm}\text{y}\hspace{0.25 cm} y_i = r \rbrace}{\# \hspace{0.1 cm}\lbrace i \hspace{0.1 cm} / \hspace{0.1 cm} x_{ij^{*(1)}} \hspace{0.05cm} \geqslant \hspace{0.05cm} s^{*(1)} \hspace{0.25 cm}\text{y}\hspace{0.25 cm} x_{ij} \hspace{0.05cm} \geqslant \hspace{0.05cm} s_3 \hspace{0.1 cm} \rbrace }\right) $$

Notese que :

$$ \left( 1 - f_{r^*_{R_{13}} , R_{13}} \right) \hspace{0.3cm} \text{y} \hspace{0.3cm} \left( 1 - f_{r^*_{R_{23}} , R_{23}} \right) $$

NO dependen de $(j, s_3)$ , por lo que puede sacarse de la funcion objetivo del problema de minimizacion sin que esto altere la solucion del problema.

Arbol tras resolver el problema de la Iteracion 3

In [ ]:
from IPython.display import Image
Image(filename='iter3.jpg', width = 900, height = 300)
Out[ ]:
  • Si alguna de las ramas tiene menos de $\hspace{0.05cm}k\hspace{0.05cm}$ observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ se para el algoritmo

  • Si todas las ramas tienen $\hspace{0.05cm}k\hspace{0.05cm}$ o mas observaciones de train $\hspace{0.1cm} \Rightarrow \hspace{0.1cm}$ el algoritmo continua, se pasa a resolver el problema de la iteracion siguiente, en este caso el de la iteracion 2

Siempre que no se cumpla la condicion de parada se seguiria haciendo crecer el arbol generando nuevas iteraciones.

No seguiremos exponiendo mas iteraciones del algoritmo, puesto que es facilmente extrapolable lo expuesto a cualquier iteracion superior.


Classification Trees en Python ¶

Algoritmo de creacion propia con TEC ¶

In [ ]:
def classification_tree(Data_set, iterations_vector, k, Y_categories) :

# POR AHORA SOLO GENERA 4 ITERACIONES EN EL ARBOL --> iterations_vector = range(1,5) como mucho (=[1,2,3,4])

# Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p

# Si se quuiere que el arbol tenga como mucho 3 iteraciones --> iterations_vector = range(1,4) = [1,2,3]

# Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

# k = numero de obsrevaciones minimas por rama del arbol --> criterio de parada

########################################################################
    
    def s_values(j, Data_set):

        s_values = []

        if  (Data_set.dtypes[j] != 'float64') & (Data_set.dtypes[j] != 'int64') : # Para las variables categoricas s_value sera simplemente su rango.

            s_values = Data_set.sort_values(by=[Data_set.columns[j]], axis=0, ascending=True, ignore_index=True).iloc[:, j].unique()


        elif (Data_set.dtypes[j] == 'float64') | (Data_set.dtypes[j] == 'int64') :

            Xj_sorted = Data_set.sort_values(by=[Data_set.columns[j]], axis=0, ascending=True, ignore_index=True).iloc[:, j].unique()

        
            for i in range(0, len(Xj_sorted)-1):

                s_values.append( (Xj_sorted[i] + Xj_sorted[i+1] ) / 2  )

    
        return s_values


########################################################################  

   ## ITERACION 1

    if iterations_vector[0] == 1 : # nacimiento del arbol

        
        ###################################
        
        def f_R11(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R11 = len(Data_set.loc[ (Data_set.iloc[:, j] < s) , : ] )

            if  cond_R11 != 0 :

                f_R11 = len( Data_set.loc[ (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / len( Data_set.loc[ (Data_set.iloc[:, j] < s) , : ] )

            
            elif cond_R11 == 0 :

                f_R11 = 0

            
            return f_R11 

        ######################################

        def f_R21(j, s, r, Data_set):

            cond_R21 = len(Data_set.loc[ (Data_set.iloc[:, j] >= s) , : ] )

            if cond_R21 != 0 :

                f_R21 = len( Data_set.loc[ (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / len( Data_set.loc[ (Data_set.iloc[:, j] >= s) , : ] )
            
            elif cond_R21 == 0 :

                f_R21 = 0

            
            return f_R21 


        ###################################

        TEC_vector = []
        j_vector = []
        s_vector = []

        j_star_vector = []
        s_star_vector = []
        TEC_star_vector = []

        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                # Busqueda de r_star_R11 :

                f_R11_r_vector = []

                for r in Y_categories:  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R11_r_vector.append( f_R11(j, s, r , Data_set) )

                f_R11_df = pd.DataFrame({'r':Y_categories  , 'f_R11':f_R11_r_vector })
        
                f_R11_df_sorted = f_R11_df.sort_values(by=['f_R11'], axis=0, ascending=False, ignore_index=True)

                r_star_R11 = f_R11_df_sorted.loc[0, 'r']


                # Busqueda de r_star_R21 :

                f_R21_r_vector = []

                for r in Y_categories:  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R21_r_vector.append( f_R21(j, s, r , Data_set) )

                f_R21_df = pd.DataFrame({'r':Y_categories  , 'f_R21':f_R21_r_vector })
        
                f_R21_df_sorted = f_R21_df.sort_values(by=['f_R21'], axis=0, ascending=False, ignore_index=True)

                r_star_R21 = f_R21_df_sorted.loc[0, 'r']


                # Calculo de TEC_1 para la combinacion (j, s) dada:

                TEC_1 = 1- f_R11(j, s, r_star_R11, Data_set) + 1- f_R21(j, s, r_star_R21, Data_set)

                TEC_vector.append(TEC_1)
                j_vector.append(j)
                s_vector.append(s)


        # Busqueda de j_star y s_star de la itracion 1:

        TEC_df = pd.DataFrame({'TEC':TEC_vector, 'j':j_vector, 's':s_vector})

        TEC_df_sorted = TEC_df.sort_values(by=['TEC'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( TEC_df_sorted.loc[0, 's'] )
        j_star_vector.append( TEC_df_sorted.loc[0, 'j'] )
        TEC_star_vector.append(TEC_df_sorted.loc[0, 'TEC'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...    
        
      ###################################

        # Condicion de parada:

        obs_r11 = len( Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0] , : ] )
        obs_r21 = len( Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0] , : ] )

        if(obs_r11 < k) | (obs_r21 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 1 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations=1

            obs_ramas = [obs_r11 , obs_r21]

       
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas ) 

            ###################

        elif (obs_r11 >= k) & (obs_r21 >= k) : # No se cumple el criterio de parada

            pass


######################################################################################

    ## ITERACION 2   ·········· POR MODIFICAR !! ·············

    if iterations_vector[1] == 2 :  # Desarrollar nodo R1 de la 1ª iteracion

        ################################################################


        def f_R12(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] < s) , : ] ) 

            if  cond_R12 != 0 :

                f_R12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R12

            
            elif cond_R12 == 0 :

                f_R12 = 0

            
            return f_R12 

        #########

        def f_R22(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] >= s) , : ] ) 

            if  cond_R22 != 0 :

                f_R22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R22

            
            elif cond_R22 == 0 :

                f_R22 = 0

            
            return f_R22 


        ###################################

        TEC_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                # Busqueda de r_star_R12 :

                f_R12_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R12_r_vector.append( f_R12(j, s, r , Data_set) )

                f_R12_df = pd.DataFrame({'r':Y_categories  , 'f_R12':f_R11_r_vector })
        
                f_R12_df_sorted = f_R12_df.sort_values(by=['f_R12'], axis=0, ascending=False, ignore_index=True)

                r_star_R12 = f_R11_df_sorted.loc[0, 'r']


                # Busqueda de r_star_R22 :

                f_R22_r_vector = []

                for r in Y_categories:  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R22_r_vector.append( f_R22(j, s, r , Data_set) )

                f_R22_df = pd.DataFrame({'r':Y_categories , 'f_R22':f_R21_r_vector })
        
                f_R22_df_sorted = f_R22_df.sort_values(by=['f_R22'], axis=0, ascending=False, ignore_index=True)

                r_star_R22 = f_R22_df_sorted.loc[0, 'r']


                # Calculo de TEC_1 para la combinacion (j, s) dada:

                TEC_1 = 1- f_R22(j, s, r_star_R12, Data_set) + 1- f_R22(j, s, r_star_R22, Data_set)

                TEC_vector.append(TEC_1)
                j_vector.append(j)
                s_vector.append(s)


        # Busqueda de j_star y s_star de la itracion 1:

        TEC_df = pd.DataFrame({'TEC':TEC_vector, 'j':j_vector, 's':s_vector})

        TEC_df_sorted = TEC_df.sort_values(by=['TEC'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( TEC_df_sorted.loc[0, 's'] )
        j_star_vector.append( TEC_df_sorted.loc[0, 'j'] )
        TEC_star_vector.append(TEC_df_sorted.loc[0, 'TEC'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,... 


      ###################################

        # Condicion de parada:

        obs_r12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] )
        obs_r22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )
        obs_r32 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) , : ] )

        if(obs_r12 < k) | (obs_r22 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 2 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations=2
            
            obs_ramas = [obs_r12 , obs_r22, obs_r32]

        
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas ) 

            ###################


        elif (obs_r12 >= k) & (obs_r22 >= k) : # No se cumple el criterio de parada

            pass



####################################################################################

## ITERACION 3

    if iterations_vector[2] == 3 :  # Desarrollar nodo R2 de la 1ª iteracion -->  considerar j_star_vector[0] y s_star_vector[0] (1ª iteracion) y >= (R2)

       #########################################

        def f_R33(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] < s) , : ] ) 

            if  cond_R33 != 0 :

                f_R33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R33

            
            elif cond_R33 == 0 :

                f_R33 = 0
            
            return f_R33

        #########

        def f_R43(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] >= s) , : ] ) 

            if  cond_R43 != 0 :

                f_R43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R43

            
            elif cond_R43 == 0 :

                f_R43 = 0

            
            return f_R43 

        
        ###################################

        TEC_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                # Busqueda de r_star_R11 :

                f_R33_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R33_r_vector.append( f_R33(j, s, r , Data_set) )

                f_R33_df = pd.DataFrame({'r':Y_categories  , 'f_R33':f_R11_r_vector })
        
                f_R33_df_sorted = f_R33_df.sort_values(by=['f_R33'], axis=0, ascending=False, ignore_index=True)

                r_star_R33 = f_R11_df_sorted.loc[0, 'r']


                # Busqueda de r_star_R21 :

                f_R43_r_vector = []

                for r in Y_categories:  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R43_r_vector.append( f_R43(j, s, r , Data_set) )

                f_R43_df = pd.DataFrame({'r':Y_categories  , 'f_R43':f_R21_r_vector })
        
                f_R43_df_sorted = f_R43_df.sort_values(by=['f_R43'], axis=0, ascending=False, ignore_index=True)

                r_star_R43 = f_R43_df_sorted.loc[0, 'r']


                # Calculo de TEC_1 para la combinacion (j, s) dada:

                TEC_1 = 1- f_R33(j, s, r_star_R33, Data_set) + 1- f_R43(j, s, r_star_R43, Data_set)

                TEC_vector.append(TEC_1)
                j_vector.append(j)
                s_vector.append(s)


        # Busqueda de j_star y s_star de la itracion 1:

        TEC_df = pd.DataFrame({'TEC':TEC_vector, 'j':j_vector, 's':s_vector})

        TEC_df_sorted = TEC_df.sort_values(by=['TEC'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( TEC_df_sorted.loc[0, 's'] )
        j_star_vector.append( TEC_df_sorted.loc[0, 'j'] )
        TEC_star_vector.append(TEC_df_sorted.loc[0, 'TEC'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,... 


      ###################################

        # Condicion de parada:

        obs_r13 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] )
        obs_r23 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )

        obs_r33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] )
        obs_r43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] )


        if(obs_r33 < k) | (obs_r43 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations = 3
            
            obs_ramas = [obs_r13, obs_r23, obs_r33 , obs_r43]

            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas ) 

            ###################


        elif (obs_r33 >= k) & (obs_r43 >= k) : # No se cumple el criterio de parada

            pass

    #######################


    ## ITERACION 4

    if iterations_vector[3] == 4 :  

       #########################################

       #########################################

        def f_R14(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] < s) , : ] ) 

            if  cond_R14 != 0 :

                f_R14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R14

            
            elif cond_R14 == 0 :

                f_R14 = 0

            
            return f_R14 

        #########

        def f_R24(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] >= s) , : ] ) 

            if  cond_R24 != 0 :

                f_R24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R24

            
            elif cond_R24 == 0 :

                f_R24 = 0

            
            return f_R24 


 ###################################

        TEC_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                # Busqueda de r_star_R11 :

                f_R14_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R14_r_vector.append( f_R14(j, s, r , Data_set) )

                f_R14_df = pd.DataFrame({'r':Y_categories  , 'f_R14':f_R11_r_vector })
        
                f_R14_df_sorted = f_R14_df.sort_values(by=['f_R14'], axis=0, ascending=False, ignore_index=True)

                r_star_R14 = f_R11_df_sorted.loc[0, 'r']


                # Busqueda de r_star_R21 :

                f_R24_r_vector = []

                for r in Y_categories:  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R24_r_vector.append( f_R24(j, s, r , Data_set) )

                f_R24_df = pd.DataFrame({'r':Y_categories  , 'f_R24':f_R21_r_vector })
        
                f_R24_df_sorted = f_R24_df.sort_values(by=['f_R24'], axis=0, ascending=False, ignore_index=True)

                r_star_R24 = f_R24_df_sorted.loc[0, 'r']


                # Calculo de TEC_1 para la combinacion (j, s) dada:

                TEC_1 = 1- f_R14(j, s, r_star_R14, Data_set) + 1- f_R24(j, s, r_star_R24, Data_set)

                TEC_vector.append(TEC_1)
                j_vector.append(j)
                s_vector.append(s)


        # Busqueda de j_star y s_star de la itracion 1:

        TEC_df = pd.DataFrame({'TEC':TEC_vector, 'j':j_vector, 's':s_vector})

        TEC_df_sorted = TEC_df.sort_values(by=['TEC'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( TEC_df_sorted.loc[0, 's'] )
        j_star_vector.append( TEC_df_sorted.loc[0, 'j'] )
        TEC_star_vector.append(TEC_df_sorted.loc[0, 'TEC'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...        


      ###################################

        # Condicion de parada:

        obs_r14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] < s_star_vector[3]) , : ] )
        obs_r24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] >= s_star_vector[3]) , : ] )

        obs_r34 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )
        obs_r44 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] )
        obs_r54 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] )


        if(obs_r14 < k) | (obs_r24 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations = 4
            
            obs_ramas = [obs_r14, obs_r24, obs_r34 , obs_r44, obs_r54]

            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas ) 

            ###################


        elif (obs_r14 >= k) & (obs_r24 >= k) : # No se cumple el criterio de parada

            print('Se ha generado el arbol mas grande permitido por el algoritmo (arbol con 4 Iteraciones)')

        # Aunque no se haya cummplido el criterio de parada como esta es la ultima Iteracion contemplada por el algoritmo, 
        # debemos calcular las metricas finales para que sean escupidas por el algoritmo. 
            
            number_iterations=4
            
            obs_ramas = [obs_r14, obs_r24, obs_r34, obs_r44, obs_r54]

            
              
            pass

    #######################
        
   
    return( number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas ) 
In [ ]:
def classification_tree_PREDICTIONS(Data_set, Y_categories, number_iterations, j_star_vector, s_star_vector, obs_ramas, x_new):

    if number_iterations == 1 :

            obs_r11 = obs_ramas[0]
            obs_r21 = obs_ramas[1]


        ### Prediccion:

            # Si x_new cae en R11 

            if x_new[j_star_vector[0] - 1] < s_star_vector[0] :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                
                def f_R11(r, Data_set):

                    cond_R11 = len(Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) , : ] )

                    if  cond_R11 != 0 :

                        f_R11 = len( Data_set.loc[  (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R11

            
                    elif cond_R11 == 0 :

                        f_R11 = 0
 
            
                    return f_R11
                


                # Busqueda de r_star_R11 :

                f_R11_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R11_r_vector.append( f_R11(r , Data_set) )

                f_R11_df = pd.DataFrame({'r':Y_categories  , 'f_R11':f_R11_r_vector })
        
                f_R11_df_sorted = f_R11_df.sort_values(by=['f_R11'], axis=0, ascending=False, ignore_index=True)

                r_star_R11 = f_R11_df_sorted.loc[0, 'r']

                y_new_predict = r_star_R11 

                
                
            # Si x_new cae en r21

            elif x_new[j_star_vector[0] - 1] >= s_star_vector[0] :  
                
                
                def f_R21(r, Data_set):

                    cond_R21 = len(Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) , : ] )

                    if cond_R21 != 0 :

                        f_R21 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R21
            
                    elif cond_R21 == 0 :

                        f_R21 = 0

                    return f_R21

            
            # Busqueda de r_star_R21 :

                f_R21_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R21_r_vector.append( f_R21(r , Data_set) )

                f_R21_df = pd.DataFrame({'r':Y_categories  , 'f_R21':f_R21_r_vector })
        
                f_R21_df_sorted = f_R21_df.sort_values(by=['f_R21'], axis=0, ascending=False, ignore_index=True)

                r_star_R21 = f_R21_df_sorted.loc[0, 'r']

                y_new_predict = r_star_R21 

    ###################################       

        
    if number_iterations == 2 :

            obs_r12 = obs_ramas[0]
            obs_r22 = obs_ramas[1]
            obs_r32 = obs_ramas[2]


        ### Prediccion:

            # Si x_new cae en R12
           
            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...


                def f_R12(r, Data_set):

 
                    cond_R12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] ) 

                    if  cond_R12 != 0 :

                        f_R12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R12

            
                    elif cond_R12 == 0 :

                        f_R12 = 0

                
            # Busqueda de r_star_R12 :

                f_R12_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R12_r_vector.append( f_R12(r , Data_set) )

                f_R12_df = pd.DataFrame({'r':Y_categories  , 'f_R12':f_R12_r_vector })
        
                f_R12_df_sorted = f_R12_df.sort_values(by=['f_R12'], axis=0, ascending=False, ignore_index=True)

                r_star_R12 = f_R12_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R12



            
            # Si x_new cae en R22

            elif (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] >= s_star_vector[1])  :

                
                def f_R22(r, Data_set):

                    cond_R22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] ) 

                    if  cond_R22 != 0 :

                        f_R22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R22

            
                    elif cond_R22 == 0 :

                        f_R22 = 0

            
                    return f_R22 

                
            # Busqueda de r_star_R22 :

                f_R22_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R22_r_vector.append( f_R22(r , Data_set) )

                f_R22_df = pd.DataFrame({'r':Y_categories  , 'f_R22':f_R22_r_vector })
        
                f_R22_df_sorted = f_R22_df.sort_values(by=['f_R22'], axis=0, ascending=False, ignore_index=True)

                r_star_R22 = f_R22_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R22


 

            # Si x_new cae en R32

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) :

                def f_R32(r, Data_set):

                        cond_R32 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) , : ] ) 

                        if  cond_R32 != 0 :

                            f_R32 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R32

            
                        elif cond_R32 == 0 :

                            f_R32 = 0
           
                        return f_R32 

                
            # Busqueda de r_star_R32 :

                f_R32_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R32_r_vector.append( f_R32(r , Data_set) )

                f_R32_df = pd.DataFrame({'r':Y_categories  , 'f_R32':f_R32_r_vector })
        
                f_R32_df_sorted = f_R22_df.sort_values(by=['f_R32'], axis=0, ascending=False, ignore_index=True)

                r_star_R32 = f_R32_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R32


        
    if number_iterations == 3:

            obs_r13 = obs_ramas[0]
            obs_r23 = obs_ramas[1]
            obs_r33 = obs_ramas[2]
            obs_r43 = obs_ramas[3]

        ### Prediccion:

            # Si x_new cae en R13

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                def f_R13(r, Data_set):

                    cond_R13 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] ) 

                    if  cond_R13 != 0 :

                        f_R13 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R13

                    elif cond_R13 == 0 :

                        f_R13 = 0

                    return f_R13

                
            # Busqueda de r_star_R13

                f_R13_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R13_r_vector.append( f_R13(r , Data_set) )

                f_R13_df = pd.DataFrame({'r':Y_categories  , 'f_R13':f_R13_r_vector })
        
                f_R13_df_sorted = f_R13_df.sort_values(by=['f_R13'], axis=0, ascending=False, ignore_index=True)

                r_star_R13 = f_R13_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R13



        # Si x_new cae en R23


            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] >= s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                
                def f_R23(r, Data_set):

                    cond_R23 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] ) 

                    if  cond_R23 != 0 :

                        f_R23 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R23

                    elif cond_R23 == 0 :

                        f_R23 = 0

                    return f_R23

                
            # Busqueda de r_star_R23

                f_R23_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R23_r_vector.append( f_R23( r , Data_set) )

                f_R23_df = pd.DataFrame({'r':Y_categories  , 'f_R23':f_R23_r_vector })
        
                f_R23_df_sorted = f_R23_df.sort_values(by=['f_R23'], axis=0, ascending=False, ignore_index=True)

                r_star_R23 = f_R23_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R23



        # Si x_new cae en R33

            if (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] < s_star_vector[2]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                def f_R33(r, Data_set):

                        cond_R33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] ) 

                        if  cond_R33 != 0 :

                            f_R33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R33

                        elif cond_R33 == 0 :

                            f_R33 = 0

                        return f_R33

                
            # Busqueda de r_star_R33

                f_R33_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R33_r_vector.append( f_R33( r , Data_set) )

                f_R33_df = pd.DataFrame({'r':Y_categories  , 'f_R33':f_R33_r_vector })
        
                f_R33_df_sorted = f_R33_df.sort_values(by=['f_R33'], axis=0, ascending=False, ignore_index=True)

                r_star_R33 = f_R33_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R33         

            

        # Si x_new cae en R43

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] >= s_star_vector[2])  :


                def f_R43(r, Data_set):

                        cond_R43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] ) 

                        if  cond_R43 != 0 :

                            f_R43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R43

                        elif cond_R43 == 0 :

                            f_R43 = 0

                        return f_R43

                
            # Busqueda de r_star_R33

                f_R43_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R43_r_vector.append( f_R43( r , Data_set) )

                f_R43_df = pd.DataFrame({'r':Y_categories  , 'f_R43':f_R43_r_vector })
        
                f_R43_df_sorted = f_R43_df.sort_values(by=['f_R43'], axis=0, ascending=False, ignore_index=True)

                r_star_R43 = f_R43_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R43


    
    if number_iterations == 4 :

            obs_r14 = obs_ramas[0]
            obs_r24 = obs_ramas[1]
            obs_r34 = obs_ramas[2]
            obs_r44 = obs_ramas[3]
            obs_r54 = obs_ramas[4]


         ### Prediccion:

            # Si x_new cae en R14

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) & (x_new[j_star_vector[3] - 1] < s_star_vector[3]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...


                def f_R14(r, Data_set):

                        cond_R14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] < s_star_vector[3]) , : ] ) 

                        if  cond_R14 != 0 :

                            f_R14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1])  & (Data_set.iloc[:, j_star_vector[3]] < s_star_vector[3]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R14

                        elif cond_R14 == 0 :

                            f_R14 = 0

                        return f_R14

                
            # Busqueda de r_star_R14

                f_R14_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R14_r_vector.append( f_R14(r , Data_set) )

                f_R14_df = pd.DataFrame({'r':Y_categories  , 'f_R14':f_R14_r_vector })
        
                f_R14_df_sorted = f_R14_df.sort_values(by=['f_R14'], axis=0, ascending=False, ignore_index=True)

                r_star_R14 = f_R14_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R14




            # Si x_new cae en R24


            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] < s_star_vector[1]) & (x_new[j_star_vector[3] - 1] >= s_star_vector[3]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                def f_R24(r, Data_set):

                        cond_R24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] >= s_star_vector[3]) , : ] ) 

                        if  cond_R24 != 0 :

                            f_R24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1])  & (Data_set.iloc[:, j_star_vector[3]] >= s_star_vector[3]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R24

                        elif cond_R24 == 0 :

                            f_R24 = 0

                        return f_R24

                
            # Busqueda de r_star_R24

                f_R24_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R24_r_vector.append( f_R24(r , Data_set) )

                f_R24_df = pd.DataFrame({'r':Y_categories  , 'f_R24':f_R24_r_vector })
        
                f_R24_df_sorted = f_R24_df.sort_values(by=['f_R24'], axis=0, ascending=False, ignore_index=True)

                r_star_R24 = f_R24_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R24



            # Si x_new cae en R34

            if (x_new[j_star_vector[0] - 1] < s_star_vector[0]) & (x_new[j_star_vector[1] - 1] >= s_star_vector[1]) :  # Ojo: el elemento j-1 de x_new es el valor de X_{j} , con j=1,2,...

                def f_R34(r, Data_set):

                        cond_R34 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] ) 

                        if  cond_R34 != 0 :

                            f_R34 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R34

                        elif cond_R34 == 0 :

                            f_R34 = 0

                        return f_R34

                
            # Busqueda de r_star_R34

                f_R34_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R34_r_vector.append( f_R34(r , Data_set) )

                f_R34_df = pd.DataFrame({'r':Y_categories  , 'f_R34':f_R34_r_vector })
        
                f_R34_df_sorted = f_R34_df.sort_values(by=['f_R34'], axis=0, ascending=False, ignore_index=True)

                r_star_R34 = f_R34_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R34


            
            # Si x_new cae en R44

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] < s_star_vector[2])  :

                def f_R44(r, Data_set):

                        cond_R44 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] ) 

                        if  cond_R44 != 0 :

                            f_R44 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R44

                        elif cond_R44 == 0 :

                            f_R44 = 0

                        return f_R44

                
            # Busqueda de r_star_R44

                f_R44_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R44_r_vector.append( f_R44(r , Data_set) )

                f_R44_df = pd.DataFrame({'r':Y_categories  , 'f_R44':f_R44_r_vector })
        
                f_R44_df_sorted = f_R44_df.sort_values(by=['f_R44'], axis=0, ascending=False, ignore_index=True)

                r_star_R44 = f_R44_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R44


            
            # Si x_new cae en R54

            elif (x_new[j_star_vector[0] - 1] >= s_star_vector[0]) & (x_new[j_star_vector[2] - 1] >= s_star_vector[2])  :

 
                def f_R54(r, Data_set):

                        cond_R54 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] ) 

                        if  cond_R54 != 0 :

                            f_R54 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R44

                        elif cond_R54 == 0 :

                            f_R54 = 0

                        return f_R54

                
            # Busqueda de r_star_R54

                f_R54_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R54_r_vector.append( f_R54(r , Data_set) )

                f_R54_df = pd.DataFrame({'r':Y_categories  , 'f_R54':f_R54_r_vector })
        
                f_R54_df_sorted = f_R54_df.sort_values(by=['f_R54'], axis=0, ascending=False, ignore_index=True)

                r_star_R54 = f_R54_df_sorted.loc[0, 'r']


                y_new_predict = r_star_R54

        


        
    return(y_new_predict)

Testeo del algoritmo ¶

In [ ]:
import numpy as np
import pandas as pd
In [ ]:
np.random.seed(123)

Y =  np.random.uniform(0,2,size=100).round()
X1 = np.random.beta(0.5, 0.5, size=100)
X2 = np.random.exponential(40, size=100)
X3 = np.random.normal(580, 100, size=100)
X4 = np.random.exponential(0.5, size=100)
X5 = np.random.uniform(0,1,size=100).round()

Data = pd.DataFrame({'Y':Y , 'X1':X1, 'X2':X2, 'X3':X3, 'X4':X4, 'X5':X5})

Data['Y'] = Data['Y'].astype('object')
Data['X5'] = Data['X5'].astype('object') # si ponemos astype('category') luego nos salen problemas en el algoritmo creado
In [ ]:
Gender_classification = pd.read_csv('gender_classification.csv')

Data_Gender = pd.DataFrame()

Data_Gender.loc[:, 'Y'] =  Gender_classification.loc[: , 'gender']
In [ ]:
Data_Gender = pd.concat( [ Data_Gender, Gender_classification.loc[: , Gender_classification.columns != 'gender'] ], axis=1)
In [ ]:
# Recoding Y using the standard format:

from sklearn.preprocessing import OrdinalEncoder

ord_enc = OrdinalEncoder()
In [ ]:
Data_Gender['Y'] = ord_enc.fit_transform(Data_Gender[['Y']])

Data_Gender['Y'] =Data_Gender['Y'].astype('object')
In [ ]:
Data_Gender.head()
Out[ ]:
Y long_hair forehead_width_cm forehead_height_cm nose_wide nose_long lips_thin distance_nose_to_lip_long
0 1.0 1 11.8 6.1 1 0 1 1
1 0.0 0 14.0 5.4 0 0 1 0
2 1.0 0 11.8 6.3 1 1 1 1
3 1.0 0 14.4 6.1 0 1 1 1
4 0.0 1 13.5 5.9 0 0 0 0
In [ ]:
Data_Gender.dtypes
Out[ ]:
Y                             object
long_hair                      int64
forehead_width_cm            float64
forehead_height_cm           float64
nose_wide                      int64
nose_long                      int64
lips_thin                      int64
distance_nose_to_lip_long      int64
dtype: object
In [ ]:
Data_Gender.head()
Out[ ]:
Y long_hair forehead_width_cm forehead_height_cm nose_wide nose_long lips_thin distance_nose_to_lip_long
0 1.0 1 11.8 6.1 1 0 1 1
1 0.0 0 14.0 5.4 0 0 1 0
2 1.0 0 11.8 6.3 1 1 1 1
3 1.0 0 14.4 6.1 0 1 1 1
4 0.0 1 13.5 5.9 0 0 0 0
In [ ]:
number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas = classification_tree(Data_Gender, range(1,5), 20 , range(0,2))
El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo 20 de observaciones por rama
In [ ]:
Data_Gender_Train = Data_Gender.sample(frac=0.8, replace=False, weights=None, random_state=555, axis=None, ignore_index=False)

Data_Gender_Test = Data_Gender.drop(Data_Gender_Train.index , )
In [ ]:
Data_Gender_Train
Out[ ]:
Y long_hair forehead_width_cm forehead_height_cm nose_wide nose_long lips_thin distance_nose_to_lip_long
4016 0.0 1 13.2 5.8 0 0 0 0
1697 0.0 0 13.9 6.5 0 0 0 0
4764 1.0 1 13.1 6.6 1 1 1 1
1892 1.0 1 15.3 5.6 1 0 1 0
2284 0.0 1 12.1 5.7 0 0 0 0
... ... ... ... ... ... ... ... ...
1639 0.0 1 11.7 5.1 0 0 1 0
2178 0.0 1 13.4 5.4 1 0 0 0
2321 1.0 1 13.3 7.1 1 1 0 0
1976 0.0 1 12.6 5.8 0 0 0 0
581 0.0 1 12.1 5.1 0 0 0 0

4001 rows × 8 columns

In [ ]:
Data_Gender_Test
Out[ ]:
Y long_hair forehead_width_cm forehead_height_cm nose_wide nose_long lips_thin distance_nose_to_lip_long
8 0.0 1 11.9 5.4 1 0 1 1
14 0.0 1 14.2 6.5 0 0 0 0
15 1.0 0 12.5 5.2 1 1 1 1
16 1.0 1 15.2 6.0 1 1 1 1
20 1.0 1 14.6 6.3 1 1 1 1
... ... ... ... ... ... ... ... ...
4983 0.0 1 12.1 5.7 0 0 0 0
4985 0.0 1 14.0 5.3 0 0 0 0
4987 1.0 1 12.1 6.2 1 1 1 1
4989 0.0 1 12.1 5.8 0 0 0 0
4999 0.0 1 13.2 6.2 0 0 0 0

1000 rows × 8 columns

In [ ]:
number_iterations, j_star_vector, s_star_vector, TEC_star_vector, obs_ramas = classification_tree(Data_Gender_Train, range(1,5), 20 , range(0,2))
El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo 20 de observaciones por rama
In [ ]:
y_predictions_vector = []

for i in range(0, len(Data_Gender_Test)) :

    x_new = Data_Gender_Test.iloc[ i , range(1, Data_Gender_Test.shape[1])]

    y_new_predict = classification_tree_PREDICTIONS(Data_Gender_Train, range(0,2), number_iterations, j_star_vector, s_star_vector, obs_ramas, x_new)

    y_predictions_vector.append(y_new_predict)
In [ ]:
# Tasa de Error de Clasificacion:

( y_predictions_vector != Data_Gender_Test.loc[:, 'Y'] ).sum()  / len(y_predictions_vector)
Out[ ]:
0.181

Comparacion con KNN:

In [ ]:
def KNN_classification( X , Y , x_new, k, distance = "Minkowski" , q=0, p1=0, p2=0, p3=0 ):

####################################################################################################################################################################################################################################################

    # Y tiene que ser una variable categorica con categorias estandar (0,1,2,...)

    # Ejemplo de Y :  Y = Gender_classification.iloc[0:20 , 7]

    # Ejemplo de como codificar Y en categorias estandar (si ya esta en el formato estandar indicado no hace falta):
      
      # for i in range(0, len(Y)):
          # if Y[i]=='Male':
          #   Y[i] = 0
          # elif Y[i]=='Female':
          #   Y[i]=1

    # X tiene que ser un panda data frame con los predictotres (X1,...,Xp). Ejemplo X = Gender_classification.iloc[0:20 , 0:7]

    # x_new tiene que ser una panda series. Ejemplo x_new = pd.Series({'long_hair': 1, 'forehead_width_cm': 4, 'forehead_height_cm': 6, 'nose_wide': 1 , 'nose_long': 1 , 'nose_long': 1 , 'lips_thin':1, 'distance_nose_to_lip_long': 1 })

####################################################################################################################################################################################################################################################

    X = pd.concat([X, x_new.to_frame().T], ignore_index=True)

    distances = []

    groups_knn = []


####################################################################################################################################################################################################################################################
    
    if distance == "Euclidean":

        def Dist_Euclidea_Python(i, j, Quantitative_Data_set): 

            Dist_Euclidea = ( ( Quantitative_Data_set.iloc[i-1, ] - Quantitative_Data_set.iloc[j-1, ] )**2 ).sum()

            Dist_Euclidea = np.sqrt(Dist_Euclidea)

            return Dist_Euclidea

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Euclidea_Python( len(X), i , X) )

    ###################################################################

    if distance == "Minkowski":

        def Dist_Minkowski_Python(i,j, q , Quantitative_Data_set):

            Dist_Minkowski = ( ( ( ( Quantitative_Data_set.iloc[i-1, ] - Quantitative_Data_set.iloc[j-1, ] ).abs() )**q ).sum() )**(1/q)

            return Dist_Minkowski

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Minkowski_Python( len(X), i , q , X) )

        

    ###################################################################

    if distance == "Canberra":

        def Dist_Canberra_Python(i,j, Quantitative_Data_set):

            numerator =  ( Quantitative_Data_set.iloc[i-1, ] - Quantitative_Data_set.iloc[j-1, ] ).abs()  

            denominator =  ( (Quantitative_Data_set.iloc[i-1, ]).abs() + (Quantitative_Data_set.iloc[j-1, ]).abs() )
       
            numerator=np.array([numerator], dtype=float)

            denominator=np.array([denominator], dtype=float)

            Dist_Canberra = ( np.divide( numerator , denominator , out=np.zeros_like(numerator), where=denominator!=0) ).sum()

            return Dist_Canberra

    ###################################################################
    
        for i in range(1, len(X)):

            distances.append( Dist_Canberra_Python( len(X), i , X) )

    ###################################################################
   
    if distance == "Pearson":

        def Dist_Pearson_Python(i, j, Quantitative_Data_set):

            Dist_Pearson = ( ( Quantitative_Data_set.iloc[i-1, ] - Quantitative_Data_set.iloc[j-1, ] )**2 / Quantitative_Data_set.var() ).sum()

            Dist_Pearson = np.sqrt(Dist_Pearson)

            return Dist_Pearson

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Pearson_Python( len(X), i , X) )

    ###################################################################
    
    if distance == "Mahalanobis":

        def Dist_Mahalanobis_Python(i, j, Quantitative_Data_set):

            # All the columns of Quantitative_Data_set must be type = 'float' or 'int' (specially not 'object'), in other case we will find 
            # dimensional problems when Python compute   x @ S_inv @ x.T

            x = (Quantitative_Data_set.to_numpy()[i-1, ] - Quantitative_Data_set.to_numpy()[j-1, ])

            x = np.array([x]) # necessary step to transpose a 1D array

            S_inv = np.linalg.inv( Quantitative_Data_set.cov() ) # inverse of covariance matrix

            Dist_Maha = np.sqrt( x @ S_inv @ x.T )  # x @ S_inv @ x.T = np.matmul( np.matmul(x , S_inv) , x.T )

            Dist_Maha = float(Dist_Maha)

            return Dist_Maha

        
    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Mahalanobis_Python( len(X), i , X) )

       

    ###################################################################
    
    if distance == "Sokal":

        a = X @ X.T
        n = X.shape[0]
        p = X.shape[1]
        ones_matrix = np.ones((n, p))
        b = (ones_matrix - X) @ X.T
        c = b.T
        d = (ones_matrix - X) @ (ones_matrix - X).T

        def Sokal_Similarity_Py(i, j):

            Sokal_Similarity = (a.iloc[i-1,j-1] + d.iloc[i-1,j-1])/p

            return Sokal_Similarity


        def Dist_Sokal_Python(i, j, Binary_Data_set):

            dist_Sokal = np.sqrt( 2 - 2*Sokal_Similarity_Py(i,j, Binary_Data_set) )

            return dist_Sokal

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Sokal_Python( len(X), i , X) )

    ###################################################################
   
    if distance == "Jaccard":

        def Jaccard_Similarity_Py(i, j, Binary_Data_Matrix):

            X = Binary_Data_Py
            a = X @ X.T
            n = X.shape[0]
            p = X.shape[1]
            ones_matrix = np.ones((n, p)) 
            b = (ones_matrix - X) @ X.T
            c = b.T
            d = (ones_matrix - X) @ (ones_matrix - X).T

            Jaccard_Similarity = a.iloc[i-1,j-1] / (a.iloc[i-1,j-1] + b.iloc[i-1,j-1] + c.iloc[i-1,j-1])
            
            return Jaccard_Similarity


        def Dist_Jaccard_Python(i, j, Binary_Data_set):

            dist_Jaccard = np.sqrt( Jaccard_Similarity_Py(i,i, Binary_Data_set) + Jaccard_Similarity_Py(i,i, Binary_Data_set) - 2*Jaccard_Similarity_Py(i,j, Binary_Data_set) )

            return dist_Jaccard

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Jaccard_Python( len(X), i , X) )

    ###################################################################
    
    if distance == "Matches":

        def alpha_py(i,j, Multiple_Categorical_Data):

            X = Multiple_Categorical_Data
            alpha = np.repeat(0, X.shape[1])

            for k in range(0, X.shape[1]) :

                if X.iloc[i-1, k] == X.iloc[j-1, k] :

                    alpha[k] = 1

                else :

                    alpha[k] = 0

            alpha = alpha.sum()

            return(alpha)


        def matches_similarity_py(i, j, Multiple_Categorical_Data):

            p = Multiple_Categorical_Data.shape[1]

            matches_similarity = alpha_py(i,j, Multiple_Categorical_Data) / p

            return(matches_similarity)


        def Dist_Matches_Py(i,j, Multiple_Categorical_Data):

            Dist_Matches = np.sqrt( matches_similarity_py(i, i, Multiple_Categorical_Data) +  matches_similarity_py(j, j, Multiple_Categorical_Data) - 2*matches_similarity_py(i, j, Multiple_Categorical_Data) )

            return( Dist_Matches )

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Matches_Py( len(X), i , X) )

    ###################################################################
   
    if distance == "Gower":

            
        def a(Binary_Data) :

            X = Binary_Data

            a = X @ X.T

            return(a)

##########################################################################################

        def d(Binary_Data):

            X = Binary_Data

            ones_matrix = np.ones(( X.shape[0] , X.shape[1])) 

            d = (ones_matrix - X) @ (ones_matrix - X).T

            return(d)

##########################################################################################

        def alpha_py(i,j, Multiple_Categorical_Data):

                X = Multiple_Categorical_Data

                alpha = np.repeat(0, X.shape[1])

                for k in range(0, X.shape[1]) :

                    if X.iloc[i-1, k] == X.iloc[j-1, k] :

                        alpha[k] = 1

                    else :

                        alpha[k] = 0


                alpha = alpha.sum()

                return(alpha)

   ##########################################################################################


        def Gower_Similarity_Python(i,j, Mixed_Data_Set, p1, p2, p3):

            X = Mixed_Data_Set

   # The data matrix X have to be order in the following way:
   # The p1 first are quantitative, the following p2 are binary categorical, and the following p3 are multiple categorical.

   #####################################################################################
        
            def G(k, X):

                range = X.iloc[:,k].max() - X.iloc[:,k].min() 

                return(range)

            G_vector = np.repeat(0, p1)

            for r in range(0, p1):

                G_vector[r] = G(r, X)
                
      
    ##########################################################################################
    
            ones = np.repeat(1, p1)

            Quantitative_Data = X.iloc[: , 0:p1]

            Binary_Data = X.iloc[: , (p1):(p1+p2)]
            
            Multiple_Categorical_Data = X.iloc[: , (p1+p2):(p1+p2+p3) ]

    ##########################################################################################

            numerator_part_1 = ( ones - ( (Quantitative_Data.iloc[i-1,:] - Quantitative_Data.iloc[j-1,:]).abs() / G_vector ) ).sum() 

            numerator_part_2 = a(Binary_Data).iloc[i-1,j-1] + alpha_py(i,j, Multiple_Categorical_Data)

            numerator = numerator_part_1 + numerator_part_2
 
            denominator = p1 + (p2 - d(Binary_Data).iloc[i-1,j-1]) + p3

            Similarity_Gower = numerator / denominator  

            return(Similarity_Gower)

##########################################################################################

        def Dist_Gower_Py(i, j, Mixed_Data , p1, p2, p3):

            Dist_Gower = np.sqrt( 1 - Gower_Similarity_Python(i, j, Mixed_Data , p1, p2, p3) )

            return(Dist_Gower)    

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_Gower_Py( len(X), i , X, p1, p2, p3) )    

######################################################################################################################################
    
    
    if distance == "Gower-BM":

        def a(Binary_Data) :

            X = Binary_Data

            a = X @ X.T

            return(a)

##########################################################################################

        def d(Binary_Data):

            X = Binary_Data

            ones_matrix = np.ones(( X.shape[0] , X.shape[1])) 

            d = (ones_matrix - X) @ (ones_matrix - X).T

            return(d)

##########################################################################################

        def alpha_py(i,j, Multiple_Categorical_Data):

                X = Multiple_Categorical_Data

                alpha = np.repeat(0, X.shape[1])

                for k in range(0, X.shape[1]) :

                    if X.iloc[i-1, k] == X.iloc[j-1, k] :

                        alpha[k] = 1

                    else :

                        alpha[k] = 0


                alpha = alpha.sum()

                return(alpha)

##########################################################################################

        def GowerBM_Similarity_Python(i,j, BM_Data_Set, p2, p3):

            X = BM_Data_Set

   # The data matrix X have to be order in the following way:
   # The p2 first are binary categorical, and the following p3 are multiple categorical.

##########################################################################################
       
            Binary_Data = X.iloc[: , 0:p2]

            Multiple_Categorical_Data = X.iloc[: , (p2):(p2+p3)]
 
##########################################################################################

 
            numerator_part_2 = a(Binary_Data).iloc[i-1,j-1] + alpha_py(i,j, Multiple_Categorical_Data)

            numerator = numerator_part_2

            denominator = (p2 - d(Binary_Data).iloc[i-1,j-1]) + p3

            Similarity_Gower = numerator / denominator  

            return(Similarity_Gower)    

##########################################################################################

        def Dist_GowerBM_Py(i, j, BM_Data ,  p2, p3):

            Dist_Gower = np.sqrt( 1 - GowerBM_Similarity_Python(i, j, BM_Data , p2, p3) )

            return(Dist_Gower)

    ###################################################################

        for i in range(1, len(X)):

            distances.append( Dist_GowerBM_Py( len(X), i , X, p2, p3) )

######################################################################################################################################


    if distance == "Gower-BQ":

        def a(Binary_Data) :

            X = Binary_Data

            a = X @ X.T

            return(a)

##########################################################################################

        def d(Binary_Data):

            X = Binary_Data

            ones_matrix = np.ones(( X.shape[0] , X.shape[1])) 

            d = (ones_matrix - X) @ (ones_matrix - X).T

            return(d)

##########################################################################################

        def GowerBQ_Similarity_Python(i,j, BQ_Data_Set, p1, p2):

            X = BQ_Data_Set

   # The data matrix X have to be order in the following way:
   # The p1 first are quantitative, the following p2 are binary categorical 

##########################################################################################
            def G(k, X):

                range = X.iloc[:,k].max() - X.iloc[:,k].min() 

                return(range)

            G_vector = np.repeat(0, p1)

            for r in range(0, p1): 

                G_vector[r] = G(r, X)
##########################################################################################
    
            ones = np.repeat(1, p1)

            Quantitative_Data = X.iloc[: , 0:p1]

            Binary_Data = X.iloc[: , (p1):(p1+p2)]
         
 
##########################################################################################

            numerator_part_1 = ( ones - ( (Quantitative_Data.iloc[i-1,:] - Quantitative_Data.iloc[j-1,:]).abs() / G_vector ) ).sum() 

            numerator_part_2 = a(Binary_Data).iloc[i-1,j-1] 
     
            numerator = numerator_part_1 + numerator_part_2

            denominator = p1 + (p2 - d(Binary_Data).iloc[i-1,j-1])  

            Similarity_Gower = numerator / denominator  

            return(Similarity_Gower)

##########################################################################################


        def Dist_GowerBQ_Py(i, j, BQ_Data ,  p1, p2):

            Dist_Gower = np.sqrt( 1 - GowerBQ_Similarity_Python(i, j, BQ_Data , p1, p2) )

            return(Dist_Gower)

##########################################################################################

        for i in range(1, len(X)):

            distances.append( Dist_GowerBQ_Py( len(X), i , X, p1, p2) )


######################################################################################################################################

######################################################################################################################################
    
    distances = pd.DataFrame({'distances': distances})

    distances = distances.sort_values(by=["distances"]).reset_index(drop=False)
        
    knn = distances.iloc[0:k , :]

    for i in knn.iloc[:,0]:

        groups_knn.append(Y.iloc[i , ])

    unique, counts = np.unique(groups_knn , return_counts=True)

    unique_Y , counts_Y = np.unique(Y , return_counts=True)

    if len(unique) == len(unique_Y) :

        proportions_groups_knn = pd.DataFrame({'proportions_groups': counts/k, 'groups': unique_Y })
    
    elif len(unique) < len(unique_Y) :

        proportions_groups_knn = pd.DataFrame({'proportions_groups': counts/k, 'groups': unique })



    prediction_group = proportions_groups_knn.sort_values(by=["proportions_groups"], ascending=False).iloc[0,:]['groups']

                                      

    return prediction_group, proportions_groups_knn  
In [ ]:
Data_Gender_Train['Y'] = Data_Gender_Train['Y'].astype('category') # Si es type 'object' nos da problemas la funcion KNN de sklearn
In [ ]:
X_train = Data_Gender_Train.iloc[:, 1:]
X_test = Data_Gender_Test.iloc[:, 1:]

Y_train = Data_Gender_Train.iloc[:, 0]
Y_test = Data_Gender_Test.iloc[:, 0]
In [ ]:
y_predictions_vector = []


for i in range(0, 100) :

    x_new = X_test.iloc[i , :]

    prediction_group, proportions_groups_knn = KNN_classification( X_train , Y_train , x_new, k=10, distance = "Minkowski" , q=2, p1=0, p2=0, p3=0 )

    y_predictions_vector.append(prediction_group)
In [ ]:
( y_predictions_vector != Data_Gender_Test.iloc[0:100, 0] ).sum()  / len(y_predictions_vector)
Out[ ]:
0.04

Tarda demasiado en hacer cross validation la funcion KNN_regression, hay que paralelizarla

Algoritmo de creacion propia con Gini ¶

In [ ]:
def classification_tree_Gini(Data_set, iterations_vector, k, Y_categories) :

# POR AHORA SOLO GENERA 4 ITERACIONES EN EL ARBOL --> iterations_vector = range(1,5) como mucho (=[1,2,3,4])

# Data_set tiene que ser tal que, su columna 0 sea Y, y la j-esima sea la variable Xj , para j=1,...,p

# Si se quuiere que el arbol tenga como mucho 3 iteraciones --> iterations_vector = range(1,4) = [1,2,3]

# Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

# k = numero de obsrevaciones minimas por rama del arbol --> criterio de parada

########################################################################
    
    def s_values(j, Data_set):

        s_values = []

        if  (Data_set.dtypes[j] != 'float64') & (Data_set.dtypes[j] != 'int64') : # Para las variables categoricas s_value sera simplemente su rango.

            s_values = Data_set.sort_values(by=[Data_set.columns[j]], axis=0, ascending=True, ignore_index=True).iloc[:, j].unique()


        elif (Data_set.dtypes[j] == 'float64') | (Data_set.dtypes[j] == 'int64') :

            Xj_sorted = Data_set.sort_values(by=[Data_set.columns[j]], axis=0, ascending=True, ignore_index=True).iloc[:, j].unique()

        
            for i in range(0, len(Xj_sorted)-1):

                s_values.append( (Xj_sorted[i] + Xj_sorted[i+1] ) / 2  )

    
        return s_values


########################################################################  

   ## ITERACION 1

    if iterations_vector[0] == 1 : # nacimiento del arbol

        
        ###################################
        
        def f_R11(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R11 = len(Data_set.loc[ (Data_set.iloc[:, j] < s) , : ] )

            if  cond_R11 != 0 :

                f_R11 = len( Data_set.loc[ (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / len( Data_set.loc[ (Data_set.iloc[:, j] < s) , : ] )

            
            elif cond_R11 == 0 :

                f_R11 = 0

            
            return f_R11 

        ######################################

        def f_R21(j, s, r, Data_set):

            cond_R21 = len(Data_set.loc[ (Data_set.iloc[:, j] >= s) , : ] )

            if cond_R21 != 0 :

                f_R21 = len( Data_set.loc[ (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / len( Data_set.loc[ (Data_set.iloc[:, j] >= s) , : ] )
            
            elif cond_R21 == 0 :

                f_R21 = 0

            
            return f_R21 


        ###################################

        G_vector = []
        j_vector = []
        s_vector = []

        j_star_vector = []
        s_star_vector = []
        G_star_vector = []

        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :


                f_R11_r_vector = []
                f_R21_r_vector = []

                for r in Y_categories:  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R11_r_vector.append( f_R11(j, s, r , Data_set)*(1 - f_R11(j, s, r , Data_set)) )

                    f_R21_r_vector.append( f_R21(j, s, r , Data_set)*(1 - f_R21(j, s, r , Data_set)) )

                                  
            # Calculo de G_1 para la combinacion (j, s) dada:

                G_R11 =  sum(f_R11_r_vector)
                G_R21 =  sum(f_R21_r_vector)

                G_1 =  G_R11 + G_R21

                G_vector.append(G_1)
                j_vector.append(j)
                s_vector.append(s)


        # Busqueda de j_star y s_star de la itracion 1:

        G_df = pd.DataFrame({'G':G_vector, 'j':j_vector, 's':s_vector})

        G_df_sorted = G_df.sort_values(by=['G'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( G_df_sorted.loc[0, 's'] )
        j_star_vector.append( G_df_sorted.loc[0, 'j'] )
        G_star_vector.append(G_df_sorted.loc[0, 'G'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...    
        
      ###################################

        # Condicion de parada:

        obs_r11 = len( Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0] , : ] )
        obs_r21 = len( Data_set.loc[ Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0] , : ] )

        if(obs_r11 < k) | (obs_r21 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 1 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations=1

            obs_ramas = [obs_r11 , obs_r21]

       
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, G_star_vector, obs_ramas ) 

            ###################

        elif (obs_r11 >= k) & (obs_r21 >= k) : # No se cumple el criterio de parada

            pass


######################################################################################

    ## ITERACION 2   ·········· POR MODIFICAR !! ·············

    if iterations_vector[1] == 2 :  # Desarrollar nodo R1 de la 1ª iteracion

        ################################################################


        def f_R12(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] < s) , : ] ) 

            if  cond_R12 != 0 :

                f_R12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R12

            
            elif cond_R12 == 0 :

                f_R12 = 0

            
            return f_R12 

        #########

        def f_R22(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] >= s) , : ] ) 

            if  cond_R22 != 0 :

                f_R22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R22

            
            elif cond_R22 == 0 :

                f_R22 = 0

            
            return f_R22 


        ###################################

        G_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

                # Busqueda de r_star_R11 :

                f_R12_r_vector = []
                f_R22_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R12_r_vector.append( f_R12(j, s, r , Data_set)*(1 - f_R12(j, s, r , Data_set)) )

                    f_R22_r_vector.append( f_R22(j, s, r , Data_set)*(1 - f_R22(j, s, r , Data_set)))


            # Calculo de G_2 para la combinacion (j, s) dada:

                G_R12 =  sum(f_R12_r_vector)
                G_R22 =  sum(f_R22_r_vector)

                G_2 =  G_R12 + G_R22

                G_vector.append(G_2)
                j_vector.append(j)
                s_vector.append(s)



        # Busqueda de j_star y s_star de la itracion 1:

        G_df = pd.DataFrame({'G':G_vector, 'j':j_vector, 's':s_vector})

        G_df_sorted = G_df.sort_values(by=['G'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( G_df_sorted.loc[0, 's'] )
        j_star_vector.append( G_df_sorted.loc[0, 'j'] )
        G_star_vector.append(G_df_sorted.loc[0, 'G'])


        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,... 


      ###################################

        # Condicion de parada:

        obs_r12 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] )
        obs_r22 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )
        obs_r32 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) , : ] )

        if(obs_r12 < k) | (obs_r22 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 2 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations=2
            
            obs_ramas = [obs_r12 , obs_r22, obs_r32]

        
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, G_star_vector, obs_ramas ) 

            ###################


        elif (obs_r12 >= k) & (obs_r22 >= k) : # No se cumple el criterio de parada

            pass



####################################################################################

## ITERACION 3

    if iterations_vector[2] == 3 :  # Desarrollar nodo R2 de la 1ª iteracion -->  considerar j_star_vector[0] y s_star_vector[0] (1ª iteracion) y >= (R2)

       #########################################

        def f_R33(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] < s) , : ] ) 

            if  cond_R33 != 0 :

                f_R33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R33

            
            elif cond_R33 == 0 :

                f_R33 = 0

            
            return f_R33

        #########

        def f_R43(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] >= s) , : ] ) 

            if  cond_R43 != 0 :

                f_R43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] >= s_star_vector[0]) & (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R43

            
            elif cond_R43 == 0 :

                f_R43 = 0

            
            return f_R43 

        
        ###################################

        G_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

 
                f_R33_r_vector = []
                f_R43_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R33_r_vector.append( f_R33(j, s, r , Data_set)*(1 - f_R33(j, s, r , Data_set)) )

                    f_R43_r_vector.append( f_R43(j, s, r , Data_set)*(1 - f_R43(j, s, r , Data_set)) )
 

            # Calculo de G_3 para la combinacion (j, s) dada:

                G_R33 =  sum(f_R33_r_vector)
                G_R43 =  sum(f_R43_r_vector)

                G_3 =  G_R33 + G_R43

                G_vector.append(G_3)
                j_vector.append(j)
                s_vector.append(s)
 


        # Busqueda de j_star y s_star de la itracion 1:

        G_df = pd.DataFrame({'G':G_vector, 'j':j_vector, 's':s_vector})

        G_df_sorted = G_df.sort_values(by=['G'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( G_df_sorted.loc[0, 's'] )
        j_star_vector.append( G_df_sorted.loc[0, 'j'] )
        G_star_vector.append(G_df_sorted.loc[0, 'G'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,... 


      ###################################

        # Condicion de parada:

        obs_r13 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) , : ] )
        obs_r23 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )

        obs_r33 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] )
        obs_r43 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] )


        if(obs_r33 < k) | (obs_r43 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations = 3
            
            obs_ramas = [obs_r13, obs_r23, obs_r33 , obs_r43]

            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, G_star_vector, obs_ramas ) 

            ###################


        elif (obs_r33 >= k) & (obs_r43 >= k) : # No se cumple el criterio de parada

            pass

    #######################


    ## ITERACION 4

    if iterations_vector[3] == 4 :  

       #########################################

       #########################################

        def f_R14(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] < s) , : ] ) 

            if  cond_R14 != 0 :

                f_R14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] < s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R14

            
            elif cond_R14 == 0 :

                f_R14 = 0

            
            return f_R14 

        #########

        def f_R24(j, s, r, Data_set):

           # Verificando si se cumplen las siguientes dos condiciones conjuntamente nos garantizamos que todas las ramas tienes observaciones de train. 
           # Es decir, no habra ninguna rama sin observaciones de train que caigan en ella.

            cond_R24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] >= s) , : ] ) 

            if  cond_R24 != 0 :

                f_R24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0]] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j] >= s) & (Data_set.loc[:, 'Y'] == r) , : ] ) / cond_R24

            
            elif cond_R24 == 0 :

                f_R24 = 0

            
            return f_R24 


 ###################################

        G_vector = []
        j_vector = []
        s_vector = []


        for j in range(1, Data_set.shape[1]) :

            for s in s_values(j, Data_set) :

 
                f_R14_r_vector = []
                f_R24_r_vector = []

                for r in Y_categories :  # Si Y tiene como categorias 0,1,2 --> Y_categories = range(0,3)

                    f_R14_r_vector.append( f_R14(j, s, r , Data_set)*(1 - f_R14(j, s, r , Data_set)) )

                    f_R24_r_vector.append( f_R24(j, s, r , Data_set)*(1 - f_R24(j, s, r , Data_set)) )


            # Calculo de G_4 para la combinacion (j, s) dada:

                G_R33 =  sum(f_R33_r_vector)
                G_R43 =  sum(f_R43_r_vector)

                G_3 =  G_R33 + G_R43

                G_vector.append(G_3)
                j_vector.append(j)
                s_vector.append(s)


        # Busqueda de j_star y s_star de la itracion 1:

        G_df = pd.DataFrame({'G':G_vector, 'j':j_vector, 's':s_vector})

        G_df_sorted = G_df.sort_values(by=['G'], axis=0, ascending=True, ignore_index=True)

        s_star_vector.append( G_df_sorted.loc[0, 's'] )
        j_star_vector.append( G_df_sorted.loc[0, 'j'] )
        G_star_vector.append(G_df_sorted.loc[0, 'G'])

        # OJO: s_star_vector[i] sera el s_star de la iteracion i+1 , para i=0,1,...
        # OJO: j_star_vector[i] sera el j_star de la iteracion i+1 , para i=0,1,...        


      ###################################

        # Condicion de parada:

        obs_r14 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] < s_star_vector[3]) , : ] )
        obs_r24 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] < s_star_vector[1]) & (Data_set.iloc[:, j_star_vector[3]] >= s_star_vector[3]) , : ] )

        obs_r34 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] < s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[1]] >= s_star_vector[1]) , : ] )
        obs_r44 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] < s_star_vector[2]) , : ] )
        obs_r54 = len( Data_set.loc[ (Data_set.iloc[:, j_star_vector[0] ] >= s_star_vector[0]) & (Data_set.iloc[:, j_star_vector[2]] >= s_star_vector[2]) , : ] )


        if(obs_r14 < k) | (obs_r24 < k) : # Si se cumple el criterio de parada


            print('El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo', k ,'de observaciones por rama')

            number_iterations = 4
            
            obs_ramas = [obs_r14, obs_r24, obs_r34 , obs_r44, obs_r54]

            
            ###################
            
            return(number_iterations, j_star_vector, s_star_vector, G_star_vector, obs_ramas ) 

            ###################


        elif (obs_r14 >= k) & (obs_r24 >= k) : # No se cumple el criterio de parada

            print('Se ha generado el arbol mas grande permitido por el algoritmo (arbol con 4 Iteraciones)')

        # Aunque no se haya cummplido el criterio de parada como esta es la ultima Iteracion contemplada por el algoritmo, 
        # debemos calcular las metricas finales para que sean escupidas por el algoritmo. 
            
            number_iterations=4
            
            obs_ramas = [obs_r14, obs_r24, obs_r34, obs_r44, obs_r54]

            
              
            pass

    #######################
        
   
    return( number_iterations, j_star_vector, s_star_vector, G_star_vector, obs_ramas ) 

Testeo del algoritmo ¶

In [ ]:
number_iterations, j_star_vector, s_star_vector, G_star_vector, obs_ramas = classification_tree_Gini(Data_Gender, range(1,5), 20 , range(0,2))
El arbol final es el arbol con 3 Iteracion. Se ha cumplido el criterio de parada basado en numero minimo 20 de observaciones por rama
In [ ]:
y_predictions_vector = []

for i in range(0, len(Data_Gender_Test)) :

    x_new = Data_Gender_Test.iloc[ i , range(1, Data_Gender_Test.shape[1])]

    y_new_predict = classification_tree_PREDICTIONS(Data_Gender_Train, range(0,2), number_iterations, j_star_vector, s_star_vector, obs_ramas, x_new)

    y_predictions_vector.append(y_new_predict)
In [ ]:
number_iterations
Out[ ]:
3
In [ ]:
j_star_vector
Out[ ]:
[4, 2, 2]
In [ ]:
s_star_vector
Out[ ]:
[0.5, 14.350000000000001, 11.45]
In [ ]:
G_star_vector
Out[ ]:
[0.42450670339433766, 0.1532375224770843, 0.20096102512866573]
In [ ]:
 obs_ramas
Out[ ]:
[2416, 115, 8, 2462]

Sklearn para arboles de clasificacion ¶